206_反转链表

本文主要是介绍206_反转链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

记录新手小白的做题过程。

题目：

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

示例 1：

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

之前没有背过这个算法，看到这道题的时候有点懵。

---

第一次尝试：

思路：创建一个新的结点等于那个要反转的结点，然后将它的后驱结点指向新结点，删除原来结点，然后循环，依次反转。

/*** 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 *p=head;ListNode *p1=p->next;ListNode *p2=p1->next;while(p->next!=nullptr){p1->next=p;p=p1;p1=p2;p2=p2->next;//如何处理P2会指向0是个问题}return p;}
};

但是这里报错了，p2在遍历时会成为最后一个结点的空指针 ，且还要继续

然后我改了一下，就是说当p1指向nullptr时，我就退出循环，在最后再反转最后一个循环。

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *p=head;ListNode *p1=p->next;ListNode *p2=p->next;while(p1->next!=nullptr){p2=p2->next;//如何处理P2会指向0是个问题p1->next=p;p=p1;p1=p2;}p1->next=p;return p1;}
};

但是还是错的，看一下别人的。

---

官方代码：

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr;ListNode* curr = head;while (curr) {//注意条件为什么是这个，当curr为最后一个节点的时候，它的next为空，而curr在最后会需要移动到那个位置ListNode* next = curr->next;//记住下一个结点用于curr移动curr->next = prev;//创造一个反转链prev = curr;//将新链表的开头结点往后移//这一步很容易忘记，不要漏了curr = next;//将curr往后移}return prev;//curr已经为空了，prev才是开头}
};

官方链接

 评论区里大佬如下：

class Solution {public ListNode reverseList(ListNode head) {ListNode ans = null;//创建新链的头结点for (ListNode x = head; x != null; x = x.next) {ans = new ListNode(x.val,ans);//创建下一个结点}return ans;}
}
//ListNode(int x, ListNode *next) : val(x), next(next) {}//这是题目给出的构造函数，创建的是这一个结点的前置结点，将链表反向重新创建

 不过这个没有反转的意思在里面，是重新建立了一个链表，将数字从前往后设置结点。

大佬解法之递归解法

递归做法

下面是视频讲解的重点 

问题可以使用递归的三个条件：1. 大问题可以拆解成两个子问题：头节点与除头结点之外剩余的链表

2.子问题的求解方式跟大问题一样，把子链表拆成除了头节点与除了头节点之外的剩余结点

3.存在最小子问题

递的过程，

归的过程，需要完成反转的过程，将head.next.next=head，指向头节点，把head.next指向空，然后返回上一级，上一级的head.next就是这一级的最后一个，继续执行反转操作，然后返回。就是在反转的时候形成一个环，然后又将环断掉形成链。

我一开始没看懂他的视频，自己照着代码研究了一下就看懂了，很精妙。我给出了自己的注释。

public:ListNode* reverseList(ListNode* head) {if (head == nullptr || head->next == nullptr) return head;//递归终止条件，已经是最后一个元素，或者只有一个元素ListNode* p = reverseList(head->next);//这是递的过程，传到下一个结点head->next->next = head;//将指向空的head->next结点指向head（即自己），现在构成了一个环head->next = nullptr;//这一步是用来断掉head指向它的next（即P结点），现在只是p指向head,而现在的head是有两个结点指着的//上面两步是用来反转，反转之后就归return p;//返回头节点，后面的递归没p什么事，p只是用来记住头节点}

 总结：递归的方法在这里虽然不是最佳的，但在此对递归又深入了解了一点。

这道题的收获很大！

这篇关于206_反转链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---