leetcode206.反转链表

题目链接

解法一：双指针迭代

使用两个指针(引用),分别标记当前遍历到的节点cur的前一个节点(pre)，和后一个节点(next),具体的操作流程请看代码：

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

因为反转链表的操作需要从头结点遍历至尾节点，所以，这个算法流程的时间复杂度为O(n)。

解法二：尾递归

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null,head);
    }

    private ListNode reverse(ListNode pre,ListNode cur){
        if(cur == null){
            return pre;
        }
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
        return reverse(pre,next);
    }
}

执行结果：

解法三：递归

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode cur = reverseList(head.next);
        // 1->2->3->4->5->null
        // cur = 5 head = 4
        head.next.next = head;
        head.next = null;
        return cur;
    }
}

执行结果：

反转链表递归的思路比较难以理解，可以参考题解
需要说明的是：

head.next.next = head;

对于这一段代码，不能写成

cur.next = head;

因为cur是最后反转链表需要返回的值，也就是原链表的尾节点，为了保证递归的一致性，应该使用示例代码的写法。
对于递归和非递归的写法比较：时间复杂度上均为O(n),但是递归写法会隐式地调用栈空间，所以更推荐双指针迭代的写法。