LeetCode刷题篇—206.反转链表
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode刷题篇—206.反转链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2587字，纯文字阅读大概需要4分钟。
内容图文
LeetCode刷题篇—206.反转链表
题目
反转一个单链表。
思路
最近因为很多链表里的问题都涉及到了递归的方法，所以又重新深入思考了一些递归的问题，今天这道题分享迭代和递归两种思路。
在链表类型的题目当中，经常用到的一个小技巧就是创建一个dummy节点，和一个记录head节点的cur节点。
一、迭代法
（1）
原本的顺序是1->2->3，初始dummy节点为NULL，即（dummy，1->2->3）*cur = head记录头节点，指向1。
当cur节点不为NULL时，始终循环：
a.创建temp节点令其为cur节点的下一个节点，即（ListNode *temp = cur->next;）（第一次循环temp节点指向2）；
b.令cur节点的下一个节点指向dummy；（第一次循环即为从1->2变为NULL<-1）
c.将dummy节点移动到cur节点处，将cur节点移动到temp节点处；
最终完成循环后将变成：NULL<-1<-2<-3<-4<-5；
返回dummy节点，注意此时的dummy节点在5的位置
（2）
还有一种迭代法较为复杂，上述的方法每次调转相邻两个数字的一个方向（即从1->2变为1<-2，再从2->3变为2<-3），而下面这种迭代法是在一次循环中从dummy->1->2->3，变成dummy->2->1->3。涉及到的节点数更多，也较为复杂。
首先创建dummy节点，ptr节点，令dummy节点的下一个节点为head节点。
在head节点不为空且head节点的下一个节点也不为空时进行循环：（可以画画图想明白这里的边界条件是为什么）
a.定义：
ListNode *nhead = head->next;//2
ListNode *ndummy = dummy->next;//1
b.令dummy节点的下一个节点指向nhead节点，即从原本的1变为了2；
c.令head节点的下一个节点指向nhead的下一个节点，即从原本的2变为了3；
d.令nhead节点的下一个节点指向ndummy，即从原本的3变为了1；
循环以上四步，最终返回dummy->next
二、递归法
如果你觉得上述的迭代法逻辑有些复杂， 你可以尝试进行这样的思考：
将反转链表这个工作拆分开，
一层拆分：1<-(2->3->4->5);
第二层：1<-2<-(3->4->5);
依次往下，
以head为null或head的下一个节点为null时作为边界条件，
返回head。
即当链表拆分到只有5的时候，结束“递”，开始“归”；
上一层是4->5，head为4，
那就要让head->next(也就是5)的下一个节点指向4，即：
head->next->next = head;
然后让head的下一个接待你指向null，这样就变成了4<-5，
再往上一层，3->4<-5，head是3，
进行同样的操作之后，4从指向null变为指向3，3指向null；
以此类推，得到最终结果。
求解方法
//迭代法
ListNode *dummy = NULL,*cur = head;
while(cur != NULL)
{
ListNode *xt = cur->next;
cur->next = dummy;
dummy = cur;
cur = xt;
}
return dummy;
这里要注意节点创建的方式，利用c++中的方法：new一个对象
ListNode *dummy = new ListNode(), *ptr = head;
dummy->next = head;
while(head != NULL && head->next != NULL)
{
ListNode *nhead = head->next;//2
ListNode *ndummy = dummy->next;//1
dummy->next = nhead;
head->next = nhead->next;
nhead->next = ndummy;
}
return dummy->next;
//递归法
if(head == NULL || head->next == NULL)
return head;
ListNode *newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
内容总结
以上是互联网集市为您收集整理的LeetCode刷题篇—206.反转链表全部内容，希望文章能够帮你解决LeetCode刷题篇—206.反转链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。