148. 排序链表（高频题）

怼烎@ 2023-10-04 08:46 6阅读 0赞

#### 148. 排序链表 ####

*  解题思路
 *  代码

## 解题思路 ##

这题想到要排序，是链表。用**快慢指针**，还需要扩展一下，**归并排序**。  
但是要注意，这里的归并排序和 给数组归并排序有一丢丢的不同，因为这个链表不支持随机访问

## 代码 ##

/**
     * 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) {
        
                return head;
            }
            return Sort(head);
        }
    
        /**
         * 返回拆分后的链表头节点，方便归并排序
         *
         * @param head
         * @return
         */
        public ListNode Sort(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;
            }
            ListNode tempNext = slow.next;
            slow.next = null;
    
            //找到两个新的起点,二路归并
            ListNode leftNode = Sort(head);
            ListNode rightNode = Sort(tempNext);
    
            return merge(leftNode, rightNode);
        }
    
        public ListNode merge(ListNode leftNode, ListNode rightNode) {
        
            ListNode prev = new ListNode(-1);//哨兵节点
            ListNode tmp = prev;
            while (leftNode != null && rightNode != null) {
        
    
                if (leftNode.val <= rightNode.val) {
        
                    prev.next = leftNode;
                    leftNode = leftNode.next;
                } else {
        
                    prev.next = rightNode;
                    rightNode = rightNode.next;
                }
                prev = prev.next;
            }
            prev.next = (leftNode == null) ? rightNode : leftNode;
    
            return tmp.next;
        }
    }