Day11--HOT100--25. K 个一组翻转链表，138. 随机链表的复制，148. 排序链表

Day11–HOT100–25. K 个一组翻转链表，138. 随机链表的复制，148. 排序链表

每日刷题系列。今天的题目是力扣HOT100题单。

题目类型：链表。

今天这几道都是比较难的题，先大胆跳过，回头再刷。

25. K 个一组翻转链表

思路：

1. 计算数组长度，每k个一组，最后不足k个的不管
2. k个内，就是常规的反转链表的套路
3. 反转完k个之后，记得”连接上邻居”，前面的邻居和后面的邻居都要连接上。

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int n = 0;
        ListNode p = head;
        while (p != null) {
            p = p.next;
            n++;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode p0 = dummy;
        ListNode pre = null;
        ListNode cur = head;

        for (; n >= k; n -= k) {
            for (int i = 0; i < k; i++) {
                ListNode temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }

            ListNode temp = p0.next;
            p0.next.next = cur;
            p0.next = pre;
            p0 = temp;
        }
        return dummy.next;
    }
}

138. 随机链表的复制

思路：

递归+哈希表。看官方题解写的，自己写不出来。

class Solution {

    Map<Node, Node> map = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        if (!map.containsKey(head)) {
            Node copy = new Node(head.val);
            map.put(head, copy);
            copy.next = copyRandomList(head.next);
            copy.random = copyRandomList(head.random);
        }

        return map.get(head);
    }
}

思路：

交替链表+分离链表。抄的，自己想不到。二刷再做。

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        for (Node cur = head; cur != null; cur = cur.next.next) {
            cur.next = new Node(cur.val, cur.next);
        }

        for (Node cur = head; cur != null; cur = cur.next.next) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
        }

        Node newHead = head.next;
        Node cur = head;
        for (; cur.next.next != null; cur = cur.next) {
            Node copy = cur.next;
            cur.next = cur.next.next;
            copy.next = copy.next.next;
        }
        cur.next = null;
        return newHead;
    }
}

148. 排序链表

思路：

递归的方法好写过迭代法。脑子转不动了，直接跳过。回头再二刷。

class Solution {
    public ListNode sortList(ListNode head) {
        // 如果链表为空或者只有一个节点，无需排序
        if (head == null || head.next == null) {
            return head;
        }
        // 找到中间节点 head2，并断开 head2 与其前一个节点的连接
        // 比如 head=[4,2,1,3]，那么 middleNode 调用结束后 head=[4,2] head2=[1,3]
        ListNode head2 = middleNode(head);
        // 分治
        head = sortList(head);
        head2 = sortList(head2);
        // 合并
        return mergeTwoLists(head, head2);
    }

    // 876. 链表的中间结点（快慢指针）
    private ListNode middleNode(ListNode head) {
        ListNode pre = head;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            pre = slow; // 记录 slow 的前一个节点
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null; // 断开 slow 的前一个节点和 slow 的连接
        return slow;
    }

    // 21. 合并两个有序链表（双指针）
    private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(); // 用哨兵节点简化代码逻辑
        ListNode cur = dummy; // cur 指向新链表的末尾
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1; // 把 list1 加到新链表中
                list1 = list1.next;
            } else { // 注：相等的情况加哪个节点都是可以的
                cur.next = list2; // 把 list2 加到新链表中
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1 : list2; // 拼接剩余链表
        return dummy.next;
    }
}