文章目录

方法一 原地反转方法二 迭代方法三 递归方法四 新建链表法

206. 反转链表

给你单链表的头节点 <code>head ，请你反转链表，并返回反转后的链表。

示例 1：

<code>输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2：

<code>输入：head = [1,2] 输出：[2,1]

示例 3：

输入：head = [] 输出：[]

提示：

链表中节点的数目范围是 [0, 5000]-5000 <= Node.val <= 5000

方法一 原地反转

本题链表不带头结点

原地反转需要两个指针，以防pre指针操作后指向上一节点而丢失指向下一节点的指针

<code>pre->next = cur->next：1.连:第一步先将pre所在节点和cur->next所在节点连接起来,将当前节点 cur 从链表中移除，并把链表连接起来。

<code>cur->next = head：2.掉:将cur的next指向head，将cur插入到head的前面,以便将其放置到链表的前面，成为新的头节点。

<code>head = cur;：3.接:更新head，使其指向当前的cur

<code>cur = pre->next：4.移:更新cur，移动到下一个待反转的节点

<code>struct ListNode* reverseList(struct ListNode* head) {

if (head == NULL) {

return head;

}

struct ListNode* cur = head->next;

struct ListNode* pre = head;

while (cur) {

pre->next = cur->next;

cur->next = head;

head = cur;

cur = pre->next;

}

return head;

}

方法二 迭代

temp保存cur的下一个节点，以防止反转时丢失链表信息。

<code>cur->next = pre;将cur的下一个指针指向pre,实现反转。

更新<code>pre为当前的cur,为下一次迭代做准备。

更新cur为保存的下一个节点temp,继续迭代。

通过不断改变指针的指向将链表进行反转。<code>pre充当新链表的头节点,当cur为NULL循环停止，返回pre

struct ListNode* reverseList(struct ListNode* head) {

struct ListNode* pre = NULL;

struct ListNode* cur = head;

while (cur != NULL) {

struct ListNode* temp = cur->next;

cur->next = pre;

pre = cur;

cur = temp;

}

return pre;

}

方法三 递归

我们可以通过迭代的方法来得到递归方法

观察reverse函数：

函数声明中pre指针指向的为NULL，cur指针指向的为head，正如递归中声明并初始化的pre和cur指针

递归结束条件为cur为NULL,返回pre

同样temp保存cur的下一个节点，以防止反转时丢失链表信息。

然后进行反转cur->next = pre;

pre 为当前已反转部分的头节点，cur为当前待反转的节点。

然后调用递归，将cur作为新的pre传入下一层，将temp作为新的cur传入下一层。

实现了链表的递归反转

struct ListNode* reverse(struct ListNode* pre, struct ListNode* cur) {

if (!cur){

return pre;

}

struct ListNode* temp = cur->next;

cur->next = pre;

//将cur作为pre传入下一层

//将temp作为cur传入下一层，改变其指针指向当前cur

return reverse(cur, temp);

}

struct ListNode* reverseList(struct ListNode* head) {

return reverse(NULL, head);

}

方法四 新建链表法

struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));

newNode->val = head->val;

新建一个链表，并初始化

newNode->next = newHead;将新节点插入到新链表的头部

<code>newHead = newNode;

<code> head = head->next;

遍历原链表，使用头插法新建链表，并不断移动<code>newHead指针，当原链表头指针指向NULL最终返回newHead

struct ListNode* reverseList(struct ListNode* head) {

struct ListNode* newHead = NULL;

while (head) {

// 创建一个新节点

struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));

newNode->val = head->val;

// 将新节点插入到新链表的头部

newNode->next = newHead;

newHead = newNode;

// 移动到原链表的下一个节点

head = head->next;

}

return newHead;

}

感谢您的阅读

如有错误烦请指正