赞
踩
记录八:力扣【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
进阶:
链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?
所以我多定义了指针,帮助记录位置,代码部分如下:
//通过测试。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* dummy_node = new ListNode(0,head); //虚节点 ListNode* cur = dummy_node->next;//改变指针方向的节点 ListNode* pred = dummy_node;//记录cur的前一个节点 ListNode* succ = nullptr;//记录cur的后一个节点 while(cur != nullptr){ //因为要获得cur->next,所以cur不能为空 succ=cur->next; cur->next = pred; //改变方向。 pred = cur; //指针后移 cur = succ; } //出while循环时,cur是空,pred是原链表的最后一个节点 head->next = cur; head = pred; //更改head,返回新链表的头 delete dummy_node; //删除虚节点 return head; //得到返回值 } };
逻辑检查:用一些边界例子带入尝试
总结,完整代码如下,通过测试:
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { if(head == nullptr){ return head; } ListNode* dummy_node = new ListNode(0,head); ListNode* cur = dummy_node->next;//改变指针方向的节点 ListNode* pred = dummy_node;//记录cur的前一个节点 ListNode* succ = nullptr;//记录cur的后一个节点 while(cur != nullptr){ succ=cur->next; cur->next = pred; pred = cur; cur = succ; } head->next = cur;//此时cur是空 head = pred; delete dummy_node; return head; } };
尝试简洁代码,用迭代实现,尝试用迭代调用实现,reverseList过程在函数内再次调用就是迭代。
没想出来流程。
目标——学习迭代。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { //if(head == nullptr){ 检查逻辑后,发现while可以包含所有情况,不用这个if判断。 // return head; //} //ListNode* dummy_node = new ListNode(0,head); ListNode* cur = head;//改变指针方向的节点 ListNode* pred = nullptr;//记录cur的前一个节点 ListNode* succ = nullptr;//记录cur的后一个节点 while(cur != nullptr){ //while内不用改 succ=cur->next; cur->next = pred; pred = cur; cur = succ; } return pred;//pred就是头节点,不用非得返回head,head只是一个名字。pred也可作为名字返回。 //head->next = cur;//此时cur是空 //head = pred; //delete dummy_node; //return head; } };
class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* cur = head; ListNode* pred = nullptr; return reverse(cur,pred); } ListNode* reverse(ListNode* cur,ListNode* pred){ if(cur == nullptr) return pred; //翻转指针 ListNode* succ = cur->next; cur->next = pred; return reverse(succ,cur);//一层一层调用reverse,当return pred时,逐层往上return。所以这行是return reverse(succ,cur) } };
网站上第三种解法递归,使链表从后向前翻转,不太明白。等想通之后补充。。。。。
很直白的是双指针法,就是记录cur的前一个节点和后一个节点。比对双指针,写出递归。
递归就是重复调用,每次调用不到最后,都要有翻转指针的动作,最后结果不做改变逐层上报。
(欢迎指正,转载表明出处)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。