算法-链表排序

约定不等于承诺〃 2024-04-18 08:05 29阅读 0赞

## 1. 链表排序 ##

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

*  Input: 4->2->1->3
 *  Output: 1->2->3->4

Example 2:

*  Input: -1->5->3->4->0
 *  Output: -1->0->3->4->5

链接：[leetcode 原题][leetcode]

## 2. 解法 ##

> 归并排序：
> 
> 1.  首先将链表从中部切分为两个部分，不断递归这个过程
> 2.  递归回溯的时候将两个链表归并为有序链表

public ListNode sortList(ListNode head) {
        
            return null == head ? null : mergeSort(head);
        }
    
        public ListNode mergeSort(ListNode head) {
        
            if (Objects.isNull(head.next)) {
        
                return head;
            }
            ListNode slow = head;
            ListNode fast = head;
            ListNode mid = null;
            while (null != fast && null != fast.next) {
        
                mid = slow;
                fast = fast.next.next;
                slow = slow.next;
            }
            // mid.next == slow, 从链表中间位置将其后的节点断开
            mid.next = null;
    
            ListNode node1 = mergeSort(head);
            ListNode node2 = mergeSort(slow);
            return mergeTwoLists(node1, node2);
        }
        
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
            if (null == l1) return l2;
            if (null == l2) return l1;
            ListNode dummyHead = new ListNode(0);
            ListNode p = dummyHead;
            while (null != l1 && null != l2) {
        
                if (l1.val > l2.val) {
        
                    p.next = l2;
                    l2 = l2.next;
                } else {
        
                    p.next = l1;
                    l1 = l1.next;
                }
                p = p.next;
            }
            p.next = null == l1 ? l2 : l1;
            return dummyHead.next;
        }

[leetcode]: https://leetcode.com/problems/sort-list/