526互联

【排序链表】（自顶向下/自底向上）归并排序、优先队列

发布时间 2023-12-27 15:05:46作者: 沙汀鱼

leetcode 148. 排序链表

自顶向下归并排序

  1. 用快慢指针找到序列中间位置
    这里要注意一个细节：始终使fast指向链表尾节点的next节点(也就是null)，这样slow指向后半段链表的起点，避免出现死循环。
    前半段链表[head, slow)，后半段[slow, fast)

  1. 合并两个排序链表（从底层递归回顶层时，返回的链表一定是排好序的）
自顶向下归并排序 
/**
 * 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 sort(head, null);
    }

    public ListNode sort(ListNode head, ListNode tail) {
        if(head == null) return null;
        if(head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode dummy = new ListNode(0, head);
        ListNode fast, slow;
        fast = slow = dummy;
        while(fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast != null) slow = slow.next;
        
        ListNode mid = slow;
        return merge(sort(head, mid), sort(mid, tail));
    }

    public ListNode merge(ListNode h1, ListNode h2) {
        if(h1 == null) return h2;
        if(h2 == null) return h1;
        
        ListNode dummy = new ListNode(0);
        ListNode res = dummy;

        while(h1 != null && h2 != null) {
            if(h1.val <= h2.val) {
                res.next = h1;
                h1 = h1.next;
            } else {
                res.next = h2;
                h2 = h2.next;
            }
            res = res.next;
        }
        if(h1 != null) res.next = h1;
        else res.next = h2;
        return dummy.next;
    }
}

自底向上排序

相当于省略自顶向下方法的递归过程，直接从底层开始向上两两合并。

最底层子链表的长度最长为1，子链表长度每合并一次，最长长度变为上一层长度的两倍

  1. 遍历链表长度[1, len)，对于每一层：
  2. 找到要合并的两个子链表的表头，将子链表与原链表断开连接
    这里定义ListNode cut(ListNode head, int len)函数，截断从head开始长度为len的链表（截断的意思是将这段子链表尾链表的next设置为null），从而得到子链表的表头和表尾
  3. 合并两个子链表
  4. 更新合并链表的连接
  5. 循环2、3、4步

  • 空间复杂度O(1)
  • 时间复杂度O(logn)
自底向上排序 
/**
 * 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 L = 0;
        ListNode tmp = head;
        while(tmp != null) {
            tmp = tmp.next;
            ++ L;
        }

        ListNode dummy = new ListNode(0, head);
        for(int len = 1; len < L; len <<= 1) {
            ListNode cur = dummy.next;
            ListNode pre = dummy;
            while(cur != null) {
                // [head1, head2) [head2, next)
                ListNode head1 = cur;
                ListNode head2 = cut(head1, len);
                ListNode next = cut(head2, len);
                cur = next;
                pre.next = merge(head1, head2);
                while(pre.next != null) {
                    pre = pre.next;
                }
            }
        }
        return dummy.next;

    }

    /* 截断从head开始长度为len的链表，返回链表尾节点的next节点 */
    public ListNode cut(ListNode head, int len) {
        -- len; //从head开始长度为len的链表尾节点需要从head跳len-1次
        while(head != null && len -- > 0) {
            head = head.next;
        }
        ListNode res = null;
        if(head != null) {
            res = head.next;
            head.next = null;
        }
        return res;
    }

    public ListNode merge(ListNode h1, ListNode h2) {
        if(h1 == null) return h2;
        if(h2 == null) return h1;
        ListNode dummy = new ListNode(0);
        ListNode res = dummy;
        while(h1 != null && h2 != null) {
            if(h1.val <= h2.val) {
                res.next = h1;
                h1 = h1.next;
            } else {
                res.next = h2;
                h2 = h2.next;
            }
            res = res.next;
        }
        if(h1 != null) res.next = h1;
        else res.next = h2;
        return dummy.next;
    }
}

优先队列方法

  1. 把链表数值全部放进优先队列中
  2. 依次读取队首元素构建升序链表
优先队列排序Integer 
/**
 * 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) {
        Queue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            return o1 - o2;
        });

        while(head != null) {
            pq.offer(head.val);
            head = head.next;
        }
        ListNode dummy = new ListNode(0);
        ListNode res = dummy;
        while(!pq.isEmpty()) {
            int val = pq.poll();
            res.next = new ListNode(val);
            res = res.next;
        }
        return dummy.next;

    }
}
  1. 将链表节点放进优先队列中
  2. 依次读取队首链表节点，重新构建链表的连接关系
优先队列排序ListNode 
/**
 * 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) {
        Queue<ListNode> pq = new PriorityQueue<>((o1, o2) -> {
            return o1.val - o2.val;
        });
        while(head != null) {
            pq.offer(head);
            head = head.next;
        }

        ListNode dummy = new ListNode(0);
        ListNode res = dummy;
        while(!pq.isEmpty()) {
            res.next = pq.poll();
            res = res.next;
            res.next = null;
        }
        return dummy.next;
    }
}