LeetCode 链表专题 4：复杂的穿针引线

下面看一个比较经典的问题“两两交换链表中的结点”。

例1：LeetCode 第 24 题：两两交换链表中的结点

传送门：英文网址：24. Swap Nodes in Pairs ，中文网址：24. 两两交换链表中的节点 。

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

说明:

• 你的算法只能使用常数的额外空间。
• 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

分析：两种方法：1、用递归来做就特别简单；2、穿针引线比较麻烦。

解法1：穿针引线做法：设计以下 4 个引用（指针）。
1、成对的结点 1 ：node1
2、成对的结点 2 ：node2
3、成对的结点 1 的前驱：p
4、成对的结点 2 的后继：next

Java 代码：

class ListNode {

    int val;
    ListNode next;

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

public class Solution {

    /**
     * 交换链表中成对的元素
     * （自己把图画出来，对于指针交换的过程就好理解了）
     *
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        ListNode dummyNode = new ListNode(0);

        dummyNode.next = head;
        ListNode p = dummyNode;
        while (p.next != null && p.next.next != null) {
            ListNode node1 = p.next;
            ListNode node2 = node1.next;
            ListNode next = node2.next;

            node1.next = next;
            node2.next = node1;
            p.next = node2;
            p = node1;
        }
        return dummyNode.next;
    }


    public ListNode createLinkedList(int[] arr) {
        ListNode head = new ListNode(arr[0]);
        ListNode current = head;
        for (int i = 1; i < arr.length; i++) {
            current.next = new ListNode(arr[i]);
            current = current.next;
        }
        return head;
    }

    public void printLinkedList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.printf("%d => ", current.val);
            current = current.next;
        }
        System.out.println("NULL ");
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        Solution solution = new Solution();
        ListNode head1 = solution.createLinkedList(arr);
        solution.printLinkedList(head1);
        ListNode reverseHead = solution.swapPairs(head1);
        solution.printLinkedList(reverseHead);
    }
}

说明：以下及其以后的动图如果没有特别说明，都来自这个伟大的 GitHub 仓库：https://github.com/MisterBooo/LeetCodeAnimation/blob/master/Readme.md。

image

解法2：如果使用递归的方法，就特别简单。

Java 代码：

/**
 * @author liwei
 * @date 18/7/4 下午9:42
 */
public class Solution2 {

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p1 = head;
        ListNode p2 = head.next;
        ListNode newHead = swapPairs(p2.next);
        // 下面这两行代码可以交换
        p1.next = newHead;
        p2.next = p1;
        return p2;
    }

}

下面这样写就更简单了：

Java 代码：

public class Solution4 {

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode first = head;
        ListNode second = head.next;
        first.next = swapPairs(second.next);
        second.next = first;
        return second;
    }

    public static void main(String[] args) {
        // 给定 1->2->3->4, 你应该返回 2->1->4->3.
        int[] nums = {1, 2, 3, 4, 5};
        ListNode head = new ListNode(nums);
        Solution solution = new Solution();
        ListNode swapPairs = solution.swapPairs(head);
        System.out.println(swapPairs);
    }
}

参考资料：https://blog.csdn.net/Koala_Tree/article/details/81476772。

练习

练习1：LeetCode 第 25 题：

传送门：英文网址：25. Reverse Nodes in k-Group ，中文网址：25. k个一组翻转链表 。

给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。

示例 :

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明 :

• 你的算法只能使用常数的额外空间。
• 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

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 + " -> ");
            cur = cur.next;
        }
        s.append("NULL");
        return s.toString();
    }
}

// 参考资料：https://blog.csdn.net/weiyongle1996/article/details/78473055

public class Solution {

    public ListNode reverseKGroup(ListNode head, int k) {
        // 使用递归写法的话，先考虑特殊情况
        if (head == null || head.next == null || k <= 1) {
            return head;
        }
        // 探测长度的结点
        ListNode tempNode = head;
        int curK = k;
        while (tempNode != null && curK != 0) {
            curK--;
            tempNode = tempNode.next;
        }
        // 如果够数了，先考虑反转
        if (curK == 0) {
            // 下面开始反转
            ListNode pre = null;
            ListNode curNode = head;
            for (int i = 0; i < k; i++) {
                ListNode nextNode = curNode.next;
                curNode.next = pre;
                pre = curNode;
                curNode = nextNode;
            }
            head.next = reverseKGroup(tempNode, k);
            return pre;
        }
        return head;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2};
        ListNode head = new ListNode(nums);
        Solution solution = new Solution();
        ListNode reverseKGroup = solution.reverseKGroup(head, 2);
        System.out.println(reverseKGroup);
    }
}

练习2：LeetCode 第 147 题：单链表的插入排序

传送门：英文网址：147. Insertion Sort List ，中文网址：147. 对链表进行插入排序 。

对链表进行插入排序。

image

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

示例 1：

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

示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

分析：这道题的题意我们感觉有那么些误导我们的意思，我们能想到从头开始找结点应该插入的位置，但感觉这种做法又不像插入排序。解决这个问题不要太死板，不要怕麻烦我觉得是解这道问题的关键（这句话感觉跟没说一个样，^_）。

1. 插入排序每次会将遍历到的一个元素插入到已经排序的部分；
2. 熟悉插入排序的朋友们都知道，这种插入过程是从后向前的，但是对于单链表来说，只保存了当前结点到下一个结点的 next 指针，并没有保存从当前结点到上一个节点的 pre 指针；
3. 我们就要变换思路了，每次都要从链表的第 1 个元素开始，找到新遍历的节点适合插入的位置，进行穿针引线；
4. 具体来说对于单链表的第 1 个元素，涉及到头结点的操作的时候，我们的做法往往是设计一个虚拟头结点，以简化编码。
   综上所述，想清楚上面的问题，写出正确的代码应该不是难事。

为一个链表实现插入排序。

LeetCode 第 147 题：单链表的插入排序-1 LeetCode 第 147 题：单链表的插入排序-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 + " -> ");
            cur = cur.next;
        }
        s.append("NULL");
        return s.toString();
    }
}

public class Solution {

    public ListNode insertionSortList(ListNode head) {
        // 先写最特殊的情况
        if (head == null) {
            return null;
        }
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode curNode = head;
        ListNode pre;
        ListNode next;
        while (true) {
            // 如果遍历下去，是顺序排列的话，那最简单了，curNode 指针向前就行了
            // 这一步是一个循环的过程
            // 暂存当前结点的下一结点
            while (curNode.next != null && curNode.val <= curNode.next.val) {
                curNode = curNode.next;
            }
            // 下面针对上一步跳出循环的两个条件进行特殊处理
            if (curNode.next == null) {
                // 如果后面没有元素了，那就说明，此时链表已经有序，可以结束我们的排序逻辑了
                break;
            } else {
                // 否则就一定满足 curNode.val > curNode.next.val; 为真
                // pre 打回到起点
                pre = dummyNode;
                next = curNode.next;
                // 把 pre 挪到可以放置 next 结点的上一个位置
                while (pre.next.val < next.val) {
                    pre = pre.next;
                }
                // 穿针引线的 3 个步骤，请见图 https://liweiwei1419.github.io/images/leetcode-solution/147-1.jpg
                // 穿针引线步骤 1
                curNode.next = next.next;
                // 穿针引线步骤 2
                next.next = pre.next;
                // 穿针引线步骤 2
                pre.next = next;
            }
        }
        return dummyNode.next;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3, 7, 9, 10, 8};
        ListNode head = new ListNode(nums);
        Solution solution = new Solution();
        ListNode insertionSortList = solution.insertionSortList(head);
        System.out.println(insertionSortList);
    }
}

等价写法：

Java 代码：

public class Solution2 {

    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return null;
        }
        // 虚拟头结点
        ListNode dummyNode = new ListNode(-1);
        ListNode preNode = dummyNode;
        // 用于遍历的指针
        ListNode curNode = head;
        ListNode next = null;
        // 没有这一步：dummyNode.next = head;
        while (curNode != null) {
            next = curNode.next;
            // 这一步是找到一个正确的位置插入，只要比 curNode 的值小，都应该跳过
            // 直到遇到第 1 个大于等于它的元素
            while (preNode.next != null && preNode.next.val < curNode.val) {
                preNode = preNode.next;
            }
            // 应该把 node 放在 pre 的下一个
            curNode.next = preNode.next;
            preNode.next = curNode;
            preNode = dummyNode;
            curNode = next;
        }
        return dummyNode.next;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3, 7, 9, 10, 8};
        ListNode head = new ListNode(nums);
        Solution2 solution2 = new Solution2();
        ListNode insertionSortList = solution2.insertionSortList(head);
        System.out.println(insertionSortList);
    }
}

练习3：LeetCode 第 148 题：单链表的排序，使用归并排序

传送门：英文网址：148. Sort List ，中文网址：148. 排序链表 。

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

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

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

写一个排序算法，用 的时间复杂度为一个链表进行排序。

对于单链表而言，归并排序是一个不错的选择。

思路1：自顶向下的归并排序。

注意1：特别注意下面这么一段：

while fast.next and fast.next.next:
    slow = slow.next
    fast = fast.next.next

说明：

• 这个方法走到这里，因为有前面的特判，所以至少得有 个结点，才可以排序。而取中点的操作，只有在“下个结点”和“下下结点”都存在的时候，才能这么做；
• 看看这个循环的循环体就明白了。

注意2：找到中间结点以后，记得把链表“从中切断”，这是符合逻辑的。

Python 代码：

class Solution:
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        if head is None or head.next is None:
            return head

        # 找到中点

        slow = head
        fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        head2 = slow.next
        slow.next = None

        lnode = self.sortList(head)
        rnode = self.sortList(head2)

        return self.__merge_two_sorted_list(lnode, rnode)

    def __merge_two_sorted_list(self, head1, head2):
        if head1 is None:
            return head2
        if head2 is None:
            return head1

        if head1.val < head2.val:
            head1.next = self.__merge_two_sorted_list(head1.next, head2)
            return head1
        else:
            head2.next = self.__merge_two_sorted_list(head1, head2.next)
            return head2

另一种写法：

特别注意，如果是

while fast and fast.next:
    p = slow
    slow = slow.next
    fast = fast.next.next

这种取法，==遇到两个结点的时候，slow 会向前走一步，但是截断得在 slow 结点之前，否则会进入死循环，按照我说的，画一个两个截点的链表就很清楚了==。

遇到死循环的时候，不要着急，还有耐心 debug，分析代码运行流程，很多时候问题就迎刃而解了。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


# 这里有个小陷阱，如果遇到问题，不要着急，代码调试就好了

class Solution:
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        if head is None or head.next is None:
            return head

        # 找到中点

        slow = head
        fast = head
        while fast and fast.next:
            p = slow
            slow = slow.next
            fast = fast.next.next

        p.next = None

        # print_node_list(head)
        # print_node_list(head2)

        lnode = self.sortList(head)
        rnode = self.sortList(slow)

        return self.__merge_two_sorted_list(lnode, rnode)

    def __merge_two_sorted_list(self, head1, head2):
        if head1 is None:
            return head2
        if head2 is None:
            return head1

        if head1.val < head2.val:
            head1.next = self.__merge_two_sorted_list(head1.next, head2)
            return head1
        else:
            head2.next = self.__merge_two_sorted_list(head1, head2.next)
            return head2


def create_node_list(arr):
    head = ListNode(arr[0])
    cur = head
    for i in range(1, len(arr)):
        cur.next = ListNode(arr[i])
        cur = cur.next
    return head


def print_node_list(head):
    while head:
        print(head.val, '->', end=' ')
        head = head.next
    print('NULL')


if __name__ == '__main__':
    arr = [4, 2, 1, 3]
    head = create_node_list(arr)
    print_node_list(head)

    solution = Solution()
    result = solution.sortList(head)
    print_node_list(result)

思路2：自底向上的归并排序。

我以前写了一个示意图，可以点这里看，思想还是很简单的。

（本节完）