LeetCode —— 排序

lalala / 2023-08-26 / 原文

148. 排序链表

一般都用归并排序，因为是单向链表，其它排序算法根据下标找元素，向前遍历等都比较困难

主函数流程是：

如果 head==null || head.next==null return head。因为 head.next == null 即只有一个元素时，不用再划分了，而且一个元素本身也是有序的，所以返回就返回这一个元素
通过找链表中点算法找到 midNode
左半数组是 head~midNode，右半数组是 midNode.next~结尾null 。因此令 rightListHead=midNode.next。此外为了使坐半链表有正确的边界，结尾指向null，把链表从中间分割开来，令 midNode.next = null
左半递归 rightHead = sortList(head) 右半递归 rightHead = sortList(rightListHead)
最后合并左半和右半两个有序链表 return merge2OrderList(leftHead, rightHead)

过程中会用到链表的两个经典算法：

合并两个有序链表：虚拟头节点，ListNode head = new ListNode(0); curPre = head 最后返回 head.next。while(p1!=null || p2!=null) if(p1==null)......
找链表中点：快指针走两步，慢指针走一步，但又一点于以前不同： 我们希望奇数个如 1 2 3 时返回 2，偶数个如 1 2 3 4 时返回 2 。因为我们认为 mid.next 是右半的起点，并且在这时候会令 mid.next = null。这与之前的不同，之前偶数个如 1 2 3 4 时希望返回 3

之前的找链表中点：奇数个如 1 2 3 时返回 2，偶数个如 1 2 3 4 时返回 3 。

private static ListNode findMidNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null) {
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
                slow = slow.next;
            }
        }
        return slow;
    }

奇数 1 2 3：初始 fast=1 slow=1 ；第一次循环：fast=2 fast=3 slow=2 ；第二次循环 fast=3 ；最后返回 slow=2
偶数 1 2 3 3：初始 fast=1 slow=1 ；第一次循环：fast=2 fast=3 slow=2 ；第二次循环 fast=4 fast=null slow=3 ；最后返回 slow=3

现在的找链表中点：奇数个如 1 2 3 时返回 2，偶数个如 1 2 3 4 时返回 2 。

private static ListNode findMidNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null) {
            fast = fast.next;
            // 这里要上一个  && fast.next != null 的条件
            if (fast != null && fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
        }
        return slow;
    }

奇数 1 2 3：初始 fast=1 slow=1 ；第一次循环：fast=2 fast=3 slow=2 ；第二次循环 fast=3 ；最后返回 slow=2
偶数 1 2 3 3：初始 fast=1 slow=1；第一次循环：fast=2 fast=3 slow=2 ；第二次循环 fast=4 因为fast.next==null退出了循环；最后返回 slow=2

/**
 * 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 || head.next == null) {
            // head.next == null 即只有一个元素时，不用再划分了，而且一个元素本身也是有序的，所以返回就返回这一个元素
            // 而且只有一个元素时，也没法找中点
            return head;
        }
        ListNode midNode = findMidNode(head);
        // 右半数组的起始是中间节点的下一个
        ListNode rightListHead = midNode.next;
       // 为了使链表有正常的边界，从中间节点断开
        midNode.next = null;
        ListNode leftHead = sortList(head);
        ListNode rightHead = sortList(rightListHead);
　　　　  // 合并两个有序链表
　　　　  ListNode list = merge2OrderList(leftHead, rightHead);
　　　　　return list;
    }

    /*
        经典链表算法：合并两个有序链表
     */
    private static ListNode merge2OrderList(ListNode head1, ListNode head2) {
        // 这个 head 是可以造的，只是为了后面可以不对头节点做特殊判断
        ListNode head = new ListNode(0);
        ListNode curPre = head;
        ListNode p1 = head1;
        ListNode p2 = head2;
        // 两个有一个没完，就继续循环，注意是 || 不是 &&
        while (p1 != null || p2 != null) {
            // list1完了。list2没完
            // 请注意：【刚开始写成了p1!=null】 应该是【p1==null】
            if (p1 == null) {
                curPre.next = p2;
                curPre = p2;
                p2 = p2.next;
            }
            // list2完了。list1没完
            else if (p2 == null) {
                curPre.next = p1;
                curPre = p1;
                p1 = p1.next;
            }
            else {
                if (p1.val <= p2.val) {
                    curPre.next = p1;
                    curPre = p1;
                    p1 = p1.next;
                }
                else {
                    curPre.next = p2;
                    curPre = p2;
                    p2 = p2.next;
                }
            }
        }
        // 最后返回 head.next，因为 head 就是个虚拟结点
        return head.next;
    }

    /*
        经典链表算法：合并两个有序链表
     */
    private static ListNode findMidNode(ListNode head) {
        // 我们希望奇数个如 1 2 3 时返回 2，偶数个如 1 2 3 4 时返回 2
        // 因为我们认为 mid.next 是右半的起点，并且在这时候会令 mid.next = null
        // 这与之前的不同，之前偶数个如 1 2 3 4 时希望返回 3
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null) {
            fast = fast.next;
            // 所以这里要上一个  && fast.next != null 的条件
            if (fast != null && fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
        }
        return slow;
    }
}

215. 数组中的第K个最大元素

堆排序

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int N = nums.length;
        // 注意这里是从 N/2-1 开始调，它的孩子已经可以包含堆的最后一个元素了
        // 注意 i>=0，因为堆顶可能也不满足堆定义
        for (int i=N/2-1;i>=0;i--) {
            heapfy(nums, N, i);
        }
        for (int i=N-1;i>=N-k;i--) {
            // 把末位元素提到顶部下标为0，堆顶最大放到末尾
            swap(nums, 0, i);
            // 现在这个新提上来的顶部下标为0的元素，不满足堆的定义，因此要调整0的位置。堆的边界是i,调整0。
            heapfy(nums, i, 0);
        }
        return nums[N-k];
    }

    private void heapfy(int[] nums, int N, int i) {
        // 先令最大的等于i
        int largest = i;
        // 左孩子
        int leftChilrd = 2*i+1;
        // 右孩子
        int rightChilrd = 2*i+2;
        // 左孩子比 largest 大
        if (leftChilrd < N && nums[leftChilrd] > nums[largest]) {
            largest = leftChilrd;
        }
        // 右孩子比 largest 大
        if (rightChilrd < N && nums[rightChilrd] > nums[largest]) {
            largest = rightChilrd;
        }
        // 说明左右孩子比 i 大，i 所处三角不满足堆的定义
        if (largest != i) {
            // 和更大的那个交换
            swap(nums, largest, i);
            // 继续调整 i 的位置(现在已经换到了largest)，直到到一个满足堆定义的地方
            heapfy(nums, N, largest);
        }
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}