LeetCode 206. 反转链表

206. 反转链表

题目链接：206. 反转链表 - 力扣（LeetCode）

题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解法一

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

 typedef struct ListNode ListNode;

//申请新节点
ListNode* SLTBuyNode(int x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->val = x;
	node->next = NULL;

	return node;
}

//头插
void STListPushFront(ListNode** pnewListHead, int oldListNodeVal)
{
    ListNode* newNode = SLTBuyNode(oldListNodeVal);
    newNode->next = *pnewListHead;
    
    //头插后不断更新头结点
    *pnewListHead = newNode;
}

struct ListNode* reverseList(ListNode* head) 
{
    //处理空链表和只有一个表头的情况
    if (head == NULL || head->next == NULL) 
    {
        return head;
    }

    //创建新列表
    ListNode* newListHead = SLTBuyNode(head->val);
    ListNode** pnewListHead = &newListHead;

    //将老链表头插进新链表
    ListNode* cur = head->next;
    while(cur)
    {
        STListPushFront(pnewListHead,cur->val);
        cur = cur->next;
    }
    return newListHead;
}

解题思路：

• 创建一个新链表，将旧链表不断头插入新链表。
• 最后形成的链表就是满足要求的新链表。

**注意：**这个解法仍有内存泄漏的问题，因为就链表的内存没有办法释放。

解法二

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) 
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;

    while (cur != NULL) 
    {
        // 1. 临时保存下一个节点，防止链表断连
        struct ListNode* next_temp = cur->next; 
        
        // 2. 反转当前节点的指针
        cur->next = prev; 
        
        // 3. 将 prev 和 cur 指针都向后移动一步
        prev = cur;
        cur = next_temp;
    }
    
    // 当循环结束时, cur 为 NULL, prev 正好是新的头节点
    return prev;
}

解题思路：

需要三个指针：

prev: 指向前一个节点，初始为 NULL。

cur: 指向当前需要反转的节点，初始为 head。

next: 临时保存 cur 的下一个节点，防止链表断裂。

思路：

遍历链表，对于每个节点 cur：

1. 用 next 保存 cur->next。
2. 将 cur 的 next 指针指向 prev，完成反转。
3. 将 prev 和 cur 向前移动一位（prev = cur, cur = next）。
4. 循环直到 cur 变为 NULL，此时 prev 就指向了新的头节点。