「力扣」第 206 题：反转链表（简单）

递归单链表

专题 6：链表

发布日期: 2017-08-21

反转一个单链表。

示例：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶：
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

方法一：穿针引线

很常规的一道问题，关键在于画图分析。

在画图的过程中，我们就可以分析出完成翻转链表这件事情，一共要用 3 个指针 pre、cur、next；
当前遍历的 cur 指针是一定有的；
当前结点的 next 结点要指到它前一个结点，所以 pre 也必须有；
迭代要继续下去，cur 结点的下一个结点也得使用一个指针 next 保存一下，其中 next 可以在 cur 确定以后初始化。
画图分析 next 指针的指向，我们注意到我们分析出来的指针指向的先后顺序，通常跟数组的元素交换操作一样，程序写出来是“头尾相连”的；
最后一定不要忘记，返回的是 pre 节点。

总结一下：

“穿针引线”法一般有 2 个步骤：
步骤 1：更新结点的 next 指针的指向；
步骤 2：更新循环变量，通常在循环一开始的时候，会预先保存下一轮要更新的结点，在循环结束的时候，直接赋值为这些变量即可。

Java 代码：

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    public ListNode(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("arr can not be empty");
        }
        this.val = nums[0];
        ListNode curr = this;
        for (int i = 1; i < nums.length; i++) {
            curr.next = new ListNode(nums[i]);
            curr = curr.next;
        }
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder();
        ListNode cur = this;
        while (cur != null) {
            s.append(cur.val);
            s.append(" -> ");
            cur = cur.next;
        }
        s.append("NULL");
        return s.toString();
    }
}

public class Solution {
    public ListNode reverseList(ListNode head) {
        // 特判
        if (head == null || head.next == null) {
            return head;
        }

        // 初始化上一个指针
        ListNode pre = null;
        // 初始化当前指针
        ListNode cur = head;
        ListNode next;
        while (cur != null) {
            // 第 1 步：先把下一轮的循环变量保存一下，为了第 3 步方便
            next = cur.next;
            // 第 2 步：实现当前节点的 next 指针的反转
            cur.next = pre;
            // 第 3 步：更新下一轮迭代的循环变量
            pre = cur;
            cur = next;
        }
        // 遍历完成以后，原来的最后一个节点就成为了 pre
        // 这个 pre 就是反转以后的新的链表的头指针
        return pre;
    }
}

复杂度分析：

时间复杂度：$O(N)$，仅仅遍历了一次链表；
空间复杂度：$O(1)$，仅仅遍历了一次链表，这里只使用了有限个的“指针”，帮助我们完成了链表的反转操作。

如果你觉得穿针引线麻烦，那就交给递归来做这件事情吧。

方法二：递归

Java 代码：

public class Solution {

    public ListNode reverseList(ListNode head) {
        // 特判
        if (head == null || head.next == null) {
            return head;
        }

        ListNode nextNode = head.next;
        ListNode newHead = reverseList(nextNode);
        nextNode.next = head;
        head.next = null;
        return newHead;
    }
}

复杂度分析：

时间复杂度：$O(N)$，仅仅遍历了一次链表；
空间复杂度：$O(N)$，递归需要消耗递归栈。

以前的笔记。

分析：分析这道问题的时候写的草稿。

LeetCode 第 206 题：反转链表

题目的要求是节点是不动的，而应该改变的是节点的 next 指针的方向。而不应该是去修改链表的值，使得这个新的链表看起来是反向的。指针变化的过程其实并不复杂，关键是我们把图画出来，需要多少个临时变量，指针变化过程也就一目了然了。我们可以看到，reverseList 的参数是一个 ListNode 类型的对象，即对象的头结点。

Java 代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */

class ListNode {

    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public class Solution {

    /**
     * 1、结合自己画的图并不难写出逻辑，把图画出来，迭代的思路就已经有了
     * 2、借助三个指针：pre、current、next 完成链表的反转
     * 3、
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        // 初始化上一个指针
        ListNode pre = null;
        // 初始化当前指针
        ListNode current = head;
        while (current != null) {
            // 第 1 步：先把 next 存起来，下一轮迭代要用到
            ListNode next = current.next;
            // 第 2 步：实现当前节点的 next 指针的反转
            current.next = pre;

            // 第 3 步：重新定义下一轮迭代的循环变量
            pre = current;
            current = next;
        }
        // 遍历完成以后，原来的最后一个节点就成为了 pre
        // 这个 pre 就是反转以后的新的链表的头指针
        return pre;
    }
}