3112、访问消失节点的最小时间

分析

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 104] 内
• $-10^5 <= Node.val <= 10^5$

进阶：你可以在 $O(n log n)$ 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

分析

链表有一个题目：合并有序链表。

通过二分思想，将最小单元的链表进行有序合并，先二分递归，然后回溯合并有序链表逐渐完成整改链表的排序！！！

二分归并排序

/**
 * 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;
        }
        // 链表只有一个元素
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        // 找到链表的中间节点
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        // 二分递归排序
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        // 有序链表合并
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    // 基础问题：合并有序链表
    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}

步进二分实现

按照二的倍数步进合并链表，直到无法拆成两个链表：

• step from 1 to $log_2^{i}$

/**
 * 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);
        // 按照二进制步进，等价于二分
        for (int subLength = 1;subLength < length;subLength <<= 1) {
            ListNode prev = dummyHead,curr = dummyHead.next;
            while(curr != null) {
                // 第一段
                ListNode head1 = curr;
                // 找到结尾节点
                for (int i = 1;i < subLength && curr.next != null;i++) {
                    curr = curr.next;
                }
                // 第二段
                ListNode head2 = curr.next;
                curr.next = null;// 链表断裂
                curr = head2;

                for (int i = 1;i < subLength && curr != null && curr.next != null;i++) {
                    curr = curr.next;
                }

                ListNode next = null;
                if (curr != null) {
                    next = curr.next;
                    curr.next = null;// 链表断裂
                }

                ListNode merged = merge(head1,head2);
                prev.next = merged;
                while(prev.next != null) {
                    prev = prev.next;
                }

                curr = next;// 链表重新连接
            }
        }
        return dummyHead.next;
    }

    // 基础问题：合并有序链表
    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com