148. Sort List

作者: DrunkPian0 | 来源:发表于2017-07-04 21:33 被阅读30次

    这题就是merge sort的链表实现。
    先看一下mergeSort:

    public class myMergeSort {
        static int number = 0;
    
        public static void main(String[] args) {
            int[] a = {26, 5, 98, 108, 28, 99, 100, 56, 34, 1, 45, 69};
            printArray("排序前:", a);
            MergeSort(a);
            printArray("排序后:", a);
        }
    
        private static void printArray(String pre, int[] a) {
            System.out.print(pre + "\n");
            for (int i = 0; i < a.length; i++)
                System.out.print(a[i] + "\t");
            System.out.println();
        }
    
        private static void MergeSort(int[] a) {
            // TODO Auto-generated method stub
            System.out.println("开始排序");
            Sort(a, 0, a.length - 1);
        }
    
        private static void Sort(int[] a, int left, int right) {
            if (left >= right)
                return;
            int mid = (left + right) / 2;
            //二路归并排序里面有两个Sort,多路归并排序里面写多个Sort就可以了
            Sort(a, left, mid);
            Sort(a, mid + 1, right);
            merge(a, left, mid, right);
        }
    
        private static void merge(int[] a, int left, int mid, int right) {
            int[] tmp = new int[a.length];
            int r1 = mid + 1;
            int tIndex = left;
            int cIndex = left;
            // 逐个归并
            while (left <= mid && r1 <= right) {
                if (a[left] <= a[r1])
                    tmp[tIndex++] = a[left++];
                else
                    tmp[tIndex++] = a[r1++];
            }
            // 将左边剩余的归并
            while (left <= mid) {
                tmp[tIndex++] = a[left++];
            }
            // 将右边剩余的归并
            while (r1 <= right) {
                tmp[tIndex++] = a[r1++];
            }
            System.out.println("第" + (++number) + "趟排序:\t");
            // TODO Auto-generated method stub
            //从临时数组拷贝到原数组
            while (cIndex <= right) {
                a[cIndex] = tmp[cIndex];
                //输出中间归并排序结果
                System.out.print(a[cIndex] + "\t");
                cIndex++;
            }
            System.out.println();
        }
    }
    

    复杂度O(nlogn)。
    这题的解法我看了https://leetcode.com/problems/sort-list/#/solutions
    前半部分divide的递归部分比较难,后半部分就是merge two sorted lists。

        public ListNode sortList(ListNode head) {
    
            if (head == null || head.next == null) {
                return head;
            }
            ListNode prev = new ListNode(-1);
            ListNode slow = head;
            ListNode fast = head;
            while (fast != null && fast.next != null) {
                prev = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            //prev把slow前面那个node跟slow之间的link断开
            prev.next = null;
            ListNode l1 = sortList(head);
            ListNode l2 = sortList(slow);
            return merge(l1, l2);
        }
    
        private ListNode merge(ListNode l1, ListNode l2) {
            ListNode node = new ListNode(-1);
            ListNode l = node;
            while (l1 != null && l2 != null) {
                if (l1.val < l2.val) {
                    l.next = l1;
                    l1 = l1.next;
                } else {
                    l.next = l2;
                    l2 = l2.next;
                }
                l = l.next;
            }
            if (l1 != null) {
                l.next = l1;
            }
            if (l2 != null) {
                l.next = l2;
            }
            return node.next;
        }
    

    相关文章

      网友评论

        本文标题:148. Sort List

        本文链接:https://www.haomeiwen.com/subject/rgaxhxtx.html