单链表排序

矫情吗；* 2022-08-20 14:16 157阅读 0赞

[https://leetcode.com/problems/sort-list/][https_leetcode.com_problems_sort-list]  
[http://www.acmerblog.com/leetcode-sort-list-5982.html][http_www.acmerblog.com_leetcode-sort-list-5982.html]

归并排序

package bigo;
    
    class ListNode{
        int val;
        ListNode next;
    
        ListNode(int x) { val = x; }
    }
    
    
    public class link_sort {
    
        private static ListNode merge(ListNode list1, ListNode list2){
            if(list1 == null) return list2;
            if(list2 == null) return list1;
    
            ListNode newHead = new ListNode(0);
    
            ListNode last = newHead;
            while(list1 != null && list2 != null){
                if(list1.val < list2.val){
                    last.next = list1;
                    list1 = list1.next;
                }else{
                    last.next = list2;
                    list2 = list2.next;
                }
    
                last = last.next;
            }
            if(list1 != null)
                last.next = list1;
            else if(list2 != null)
                last.next = list2;
    
            return newHead.next;
    
        }
    
        private static ListNode sortList(ListNode head){
            if(head == null || head.next == null)  return head;
    
            ListNode slow = head;
            ListNode fast = head;
    
            while(fast.next != null && fast.next.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
            //经过上面的移动后， slow 就到了中间了 。 因为fast每次移动两步，slow每次移动一步。
    
            ListNode list2 = slow.next;
            slow.next = null;
            //将链表分成两条。 head 和 list2
    
            head = sortList(head);
            list2 = sortList(list2);
    
            return merge(head, list2);
    
    
        }
    
        public static void  main(String [] arg){
            ListNode l1 = new ListNode(8);
            ListNode l2 = new ListNode(7);
            ListNode l3 = new ListNode(5);
            ListNode l4 = new ListNode(4);
            ListNode l5 = new ListNode(1);
    
            l1.next = l2;
            l2.next = l3;
            l3.next = l4;
            l4.next = l5;
    
            l1 = sortList(l1);
    
            while(l1 != null){
                System.out.println(l1.val + " ");
                l1 = l1.next;
            }
    
        }
    
    
    }

[https_leetcode.com_problems_sort-list]: https://leetcode.com/problems/sort-list/
[http_www.acmerblog.com_leetcode-sort-list-5982.html]: http://www.acmerblog.com/leetcode-sort-list-5982.html