206. 反转链表
给你单链表的头节点
head
,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2] 输出:[2,1]
示例 3:
输入:head = [] 输出:[]
提示:
- 链表中节点的数目范围是
[0, 5000]
-5000 <= Node.val <= 5000
方法一 原地反转
本题链表不带头结点
原地反转需要两个指针,以防pre
指针操作后指向上一节点而丢失指向下一节点的指针
pre->next = cur->next
:1.连:第一步先将pre
所在节点和cur->next
所在节点连接起来,将当前节点 cur
从链表中移除,并把链表连接起来。cur->next = head;
2.掉:将cur的next指向head,将cur插入到head的前面,以便将其放置到链表的前面,成为新的头节点。
head = cur;
3.接:更新head,使其指向当前的cur
cur = pre->next;
4.移:更新cur,移动到下一个待反转的节点
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
的下一个节点,以防止反转时丢失链表信息。
cur->next = pre;
将cur
的下一个指针指向pre
,实现反转。
更新pre
为当前的cur
,为下一次迭代做准备。
更新cur
为保存的下一个节点temp
,继续迭代。
通过不断改变指针的指向将链表进行反转。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;
将新节点插入到新链表的头部
newHead = newNode;
head = head->next;
遍历原链表,使用头插法新建链表,并不断移动newHead
指针,当原链表头指针指向NULL
最终返回newHead
文章来源:https://www.toymoban.com/news/detail-841704.html
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;
}
感谢您的阅读文章来源地址https://www.toymoban.com/news/detail-841704.html
到了这里,关于反转链表的四种方法(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!