每日杂记 day8

算法题

链表的归并排序

关键在于分割点的寻找和边界的选择。

1. 快慢指针找中点
2. 起始以空节点为右侧边界，保证分割点始终置于右半区域。
3. 当下一个节点为右边界时，此时只剩一个节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        // 空节点也可以视为链表的节点，用来控制左右边界
        return sortList(head, null);
    }
    public ListNode sortList(ListNode head, ListNode tail){
        if(head == null){
            return head;
        }
        // 一个元素时（排除tail），即永远取左边的值
        if(head.next == tail){
            // 销毁后继节点
            head.next = null;
            return head;
        }
        // 快慢指针找中点
        ListNode slow, fast;
        slow = fast = head;
        while(fast != tail){
            slow = slow.next;
            fast = fast.next;
            // 一步一步走，当fast下一步是尾巴时，slow已经是中点了
            if(fast != tail){
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        // 继续分治
        ListNode l1 = sortList(head, mid);
        ListNode l2 = sortList(mid, tail);
        return merge(l1, l2);
    }
    public ListNode merge(ListNode l1, ListNode l2){
        // 重新建立链表
        ListNode head = new ListNode(0);
        ListNode cur = head, cur1 = l1, cur2 = l2;
        while(cur1 != null && cur2 != null){
            if(cur1.val <= cur2.val){
                cur.next = cur1;
                cur1 = cur1.next;
            } else {
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        if(cur1 != null){
            cur.next = cur1;
        } else {
            cur.next = cur2;
        }
        return head.next;
    }
}

链表的归并排序【非递归版】

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    // 本质是“主动的”分治
    public ListNode sortList(ListNode head) {
        if(head == null){
            return head;
        }
        // 记录链表长度
        int length = 0;
        ListNode node = head;
        while(node != null){
            length++;
            node = node.next;
        }
        // 构建假头节点
        ListNode dummyHead = new ListNode(0, head);
        // 将整体分割为 n 个长度 1 为的链表开始，一一排序merge构成n个长度2的链表。
        // 然后继续分割 n 个长度为 1*2 的链表（有序），再次merge（一定满足相对顺序）
        for(int subLen=1; subLen < length; subLen *= 2){
            // cur为第一个节点
            ListNode pre = dummyHead, cur = dummyHead.next;
            while(cur != null){
                // 拼接出第一个 subLen 链表
                ListNode head1 = cur;
                for(int i=1; i<subLen && cur.next != null; i++){
                    cur = cur.next;
                }
                // 先记录第二个的起点
                ListNode head2 = cur.next;
                // 断开第一个与剩下节点的连接
                cur.next = null;
                // 拼接第二个 subLen 链表
                cur = head2;
                // cur.next != null 让 cur 至少是最后一个节点
                for(int i=1; i<subLen && cur != null && cur.next != null; i++){
                    cur = cur.next;
                }
                // 保留剩下的节点
                ListNode next = null;
                if(cur != null) {
                    next = cur.next;
                    // 断开第二个的多余连接
                    cur.next = null;
                }
                // merge 两个有序链表并连接
                pre.next = merge(head1, head2);
                // 移动 pre 到最后一个位置
                while(pre.next != null){
                    pre = pre.next;
                }
                // 继续切割下一组
                cur = next;
            }
            // ...重复切割，直到 subLen>=length 完成整个链表的排序。
        }
        return dummyHead.next;
    }
    
    public ListNode merge(ListNode l1, ListNode l2){
        // 重新建立链表
        ListNode head = new ListNode(0);
        ListNode cur = head, cur1 = l1, cur2 = l2;
        while(cur1 != null && cur2 != null){
            if(cur1.val <= cur2.val){
                cur.next = cur1;
                cur1 = cur1.next;
            } else {
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        if(cur1 != null){
            cur.next = cur1;
        } else {
            cur.next = cur2;
        }
        return head.next;
    }
}

K 个一组翻转链表

关键在于如何反转完每一组后，新的尾节点能够接上下一组。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode hair = new ListNode(0, head);
        // 用于连接新的头节点
        ListNode pre = hair;
        while(head != null){
            ListNode tail = pre;
            // 移动到分组的最后一个元素
            for(int i=0; i<k; i++) {
                tail = tail.next;
                // 如果变为了空表示长度过短直接返回（始终是连着的）
                if(tail == null){
                    return hair.next;
                }
            }
            // 保留下一个分组的节点
            // ListNode nex = tail.next;
            // 反转分组链表，接收该分组新的头尾节点（尾节点已连接下一分组）
            ListNode[] reverse = myReverse(head, tail);
            head = reverse[0];
            tail = reverse[1];
            // 连接反转后的分组链表
            pre.next = head;
            // pre设为该分组的最后一个节点，用于连接下一分组
            pre = tail;
            // 继续反转
            head = tail.next;
        }
        return hair.next;
    }
    public ListNode[] myReverse(ListNode head, ListNode tail){
        // 起始值顺势连接下一段分组
        ListNode pre = tail.next;
        // 开始反转
        ListNode p = head;
        // 正常方向 tail 本是尾巴，但是从 head 开始逐一遍历反转连接时，pre 会移动到 tail 的位置。
        while(pre != tail){
            ListNode next = p.next;
            p.next = pre;
            pre = p;
            p = next;
        }
        return new ListNode[]{tail, head};
    }
}

反转算法：以尾节点为条件，反转链表。