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;