LeetCode 单链表专题 1：在链表中穿针引线

准备算法面试一定不能忽略基础，算法面试中链表的问题是经常出现的。

链表是一种特殊的线性结构，由于不能像数组一样进行随机的访问，所以和链表相关的问题有他自身的特点。我将之称为穿针引线。我们在这一章，就来看一看，如何在链表中穿针引线。

例1：LeetCode 第 206 题：反转链表

传送门：反转链表。

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

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

[站外图片上传中...(image-448955-1558822745594)]

题目的要求是节点是不动的，而应该改变的是节点的 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;
    }
}

看看代码是不是很简单。这个解法的时间复杂度是 ，因为它仅仅遍历了一次链表，空间复杂度是，因为这里仅仅使用了有限个的“指针”，帮助我们完成了链表的反转操作。

补充：如果不使用“穿针引线”，还可以用递归完成。

练习1：LeetCode 第 92 题：反转从位置 m 到 n 的链表，k 个组进行一次反转

传送门：英文网址：92. Reverse Linked List II ，中文网址：92. 反转链表 II 。

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

LeetCode 第 92 题：反转从位置 m 到 n 的链表，k 个组进行一次反转-1

Java 代码：

class ListNode {
    int val;
    ListNode next;

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

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // 创建一个虚拟的结点（dummy）
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode pre = dummy;
        int k = 0;

        while (++k < m) {
            if (pre != null) {
                pre = pre.next;
            }
        }

        // tail 是尾巴的意思
        ListNode tail = pre.next;
        while (++k <= n) {
            ListNode temp = pre.next;

            pre.next = tail.next;
            tail.next = tail.next.next;
            pre.next.next = temp;
        }
        return dummy.next;
    } 
}

Java 代码：

public class Solution2 {

    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 0; i < m - 1; i++) {
            // pre 指针向后移动
            pre = pre.next;
        }
        // System.out.println(pre.val);

        ListNode p = pre.next;
        ListNode curNode;
        for (int i = 0; i < n - m; i++) {
            curNode = p.next;
            p.next = curNode.next;
            curNode.next = pre.next;
            pre.next = curNode;
        }
        return dummy.next;
    }
}

Java 代码：

public ListNode reverseBetween(ListNode head, int m, int n) {
    // 设置 dummyNode 是这一类问题的一般做法
    ListNode dummyNode = new ListNode(-1);
    dummyNode.next = head;
    ListNode pre = dummyNode;
    for (int i = 0; i < m - 1; i++) {
        pre = pre.next;
    }
    ListNode cur = pre.next;
    ListNode next;
    for (int i = 0; i < n - m; i++) {
        next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    return dummyNode.next;
}

另一种解法：来自“小吴”的动图，比较自然，但是代码写起来不够简洁。

图示：

LeetCode 第 92 题：反转从位置 m 到 n 的链表，k 个组进行一次反转-2

Python 代码：

LeetCode 第 92 题：反转从位置 m 到 n 的链表，k 个组进行一次反转-3

（本节完）