[数据结构与算法]LeetCode 206 反转链表 -- 递归法和双指针法

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list

给你单链表的头节点 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

思路：

最开始我自己的写法是使用递归的方法，核心代码（rListTail代表当前反转链表的尾节点）：

reverse(rnNode.next);
rListTail.next = rnNode;
rListTail = rnNode;

在每次递归当中，先将当前节点的next节点作为递归函数的参数进行递归，生成当前的反转链表（即原链表在当前节点后面的节点反转得到的反转链表），然后再将当前反转链表的尾节点的next节点设为当前节点，最后再将当前节点作为当前反转链表的尾节点。

在这道题中出现了两次问题，一次是因为忘记将尾节点的next节点设为null，原链表的head节点最后变成反转链表的尾节点后，应该将它的next节点设为null，不过我在后边也修改成了在每次修改rListTail的值后将rListTail的next节点设为null。

另一个问题是要注意题目输入的链表有可能是空链表，这时候只要返回null就可以了。

递归法Java代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    private ListNode rListHead,rListTail;//分别表示当前反转链表的头节点和尾节点
    private void reverse(ListNode rnNode){
        if(rnNode == null){
            //这个时候传入的原始链表是空链表
            rListHead = null;
            return;
        }
        if(rnNode.next == null){
            //这时候意味着已经遍历到了原链表的尾节点，此时要将其设为当前反转链表的头节点和尾节点
            rListHead = rnNode;
            rListTail = rnNode;
            return;
        }
        reverse(rnNode.next);
        rListTail.next = rnNode;
        rListTail = rnNode;
        rListTail.next = null;//别忘了将当前反转链表尾部的next指针设为null
    }
    public ListNode reverseList(ListNode head) {
        reverse(head);
        return rListHead;
    }
}

另一种解法（双指针法）：

参考文章：??????听说过两天反转链表又写不出来了？

看了参考文章后发现还可以使用双指针来做这道题，而且代码量也更少，也没有递归法抽象，更容易理解。

以下这个图很形象地展现了使用双指针的过程（图片转自代码随想录）

?双指针法Java代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head, tmp;
        while(cur != null){
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}