206反转链表

写在前面

• 这篇的原文也在搭建博客中不幸牺牲
• 但是我还会简单注释一下
• 反转链表的作用很多，可以当作别的题目的子函数，比如回文，分隔等等

下面是题目

下面是题目给出的代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    ListNode* swapPairs(ListNode* head)
    {
    }
};

• 这里我会给出三种解法，分别是迭代法，递归法和双指针法

1.迭代法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur = NULL;
        ListNode *p = head;
        while(p !=NULL)
        {
            //首先令一个临时节点指向 p后面的一个节点
            ListNode *temp = p->next;
            //然后改变p的指针，当p为头节点的时候，那么p指向空。最后，原来的头节点就是尾巴节点
            //原来的尾节点就是新链表的头节点
            p->next =cur;
            //然后每次要更新cur节点和p节点
            cur=p;
            p = temp;
        }
        return cur;
    }
};

2. 递归法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next ==NULL)
            return head;
        ListNode*ret = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return ret;
    }
};

3.双指针法

//双指针法比较巧妙
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
    if(head==NULL)
        return head;
    ListNode *cur =head;
    while(head->next!=NULL)
    {//接下来的注释是基于第一次变换的
        //仍然令一个临时节点，让他指向头结点的下下个节点，方便节点更新
        //注意，这时候原链表的结构还没有发生改变
        ListNode*t =head->next->next;
        //然后这个操作是让第二个节点指向cur，在这里暂时形成了一个闭环
        head->next->next = cur;
        //然后实现head指针的断裂，这时候其实是一个自环
        cur = head->next;
        //最后，更新head的指针，让他指向t
        head->next = t;
    }
 //接下来的每一次循环，都实现了一次链表的暂时闭环和cur节点的移动
//同时，head->next也一步步指向尾节点
//最后，cur节点成功成为尾节点，并且cur前面的所有指针都实现了反指
    return cur;
}
};