从归并排序引申到排序链表

归并排序

递归版

    //合并排序
    public static void mergeSort(int[] nums) {
        mergeSortHelper(0, nums.length, nums); //没有-1
    }

    private static void mergeSortHelper(int low, int high, int[] nums) {
        if (low >= high || high - low == 1) { //区间为空区间或只有一个元素，不用排序
            return;
        }
        int mid = (low+high)/2;
        //递归对子区间归并排序
        mergeSortHelper(low, mid, nums);//[low, mid)
        mergeSortHelper(mid, high, nums);//[mid, high)
        merge(low, mid, high, nums);
    }

    //合并两个有序数组
    private static void merge(int low, int mid, int high, int[] nums) {
        int i = low;
        int j = mid;
        int t = high - low;
        int[] extra = new int[t];
        int k = 0;
        while (i < mid && j < high) {
            //保证稳定性
            if (nums[i] <= nums[j]) {
                extra[k++] = nums[i++];
            } else {
                extra[k++] = nums[j++];
            }
        }

        while (i < mid) {
            extra[k++] = nums[i++];
        }
        while (j < high) {
            extra[k++] = nums[j++];
        }

        for (int x = 0; x < t; x++) {
            
            nums[low+x] = extra[x];
        }
    }

非递归版

    //非递归版本
    public static void mergeSort2(int[] nums) {
        //1.将数组拆分为若干个长度为size的子数组
        for (int size = 1; size < nums.length; size *= 2) {
            //1.1循环，开始对子数组操作
            for (int i = 0; i < nums.length; i += 2*size) {
                //1.1.1得到子数组n1
                int n1 = i;
                //1.1.2得到子数组n2
                int n2 = i+size;
                if (n2 > nums.length) {
                    continue;
                }
                //1.1.3去掉n1 n2的内容之后原数组剩余的内容用next保存
                int next = n2 + size;
                if (next > nums.length) {
                    next = nums.length;
                }
                merge(nums, n1, n2, next);
            }
        }
    }

排序链表

OJ链接

递归版

public class $148 {
    //法一：使用递归，自顶向下归并排序
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    private ListNode sortList(ListNode head, ListNode tail) {
        //链表为空
        if (head == null) {
            return head;
        }

        //链表只有一个节点
        if (head.next == tail) {
            head.next = null;
            return head;
        }

        //1.找到链表的中间节点（返回第二个中间节点）
        ListNode fast = head;
        ListNode slow = head;
        while (fast != tail && fast.next != tail) { //tail
            fast = fast.next.next;
            slow = slow.next;
        }

        //2.对两个子链表分别排序
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);

        //3.合并两个已排序子链表
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    private ListNode merge(ListNode list1, ListNode list2) {
        ListNode mergedHead = new ListNode(0);
        ListNode temp = mergedHead;
        ListNode temp1 = list1;
        ListNode temp2 = list2;

        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 {
            temp.next = temp2;
        }

        return mergedHead.next;
    }
}

非递归版

public class $148 {
    //法二：自底向上归并排序
    public ListNode sortList2(ListNode head) {
        //1.得到链表长度
        int len = 0;
        ListNode node = head;
        while (node != null) {
            node = node.next;
            len++;
        }

        //2.引入虚拟头结点，连接head
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        //3将链表拆分为若干个长度为size的子链表
        for (int size = 1; size < len; size *= 2) {
            //3.1prev，cur
            ListNode prev = dummyHead;
            ListNode cur = dummyHead.next;

            //3.2循环，开始对子链表进行操作
            while (cur != null) {
                //3.2.1得到长度为size的链表l1
                ListNode l1 = cur;
                for (int i = 1; i < size && cur.next != null; i++) {
                    cur = cur.next;
                }

                //3.2.2得到长度为size的链表l2，并切断两个链表的连接
                ListNode l2 = cur.next;
                cur.next = null;
                cur = l2;
                for (int i = 1; i < size && cur != null && cur.next != null; i++) {
                    cur = cur.next;
                }

                //3.2.3去掉链表1链表2之后原链表剩余的内容用next保存
                //同时切断next与两个链表的连接
                ListNode next = null;
                if (cur != null) {
                    next = cur.next;
                    cur.next = null;
                }


                //3.2.4合并两个排序链表得到merged
                ListNode merged = merge(l1, l2);

                //3.2.5prev连上merged，将prev指向merged的末尾
                prev.next = merged;
                while (prev.next != null) {
                    prev = prev.next;
                }

                //3.2.6cur指向next
                cur = next;
            }
        }
        return dummyHead.next;
    }
  
      private ListNode merge(ListNode list1, ListNode list2) {
        ListNode mergedHead = new ListNode(0);
        ListNode temp = mergedHead;
        ListNode temp1 = list1;
        ListNode temp2 = list2;

        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 {
            temp.next = temp2;
        }

        return mergedHead.next;
    }
}