题目 leetcode-148-排序链表

https://leetcode-cn.com/problems/sort-list/description/

归并排序实现

下面是关键点

• 将链表从中间节点拆分为左右2个链表，直到只有一个节点，这个时候肯定是有序的
• 合并已经排序好的2个链表
• 找到中间节点使用快慢指针的方式

/*
 * @lc app=leetcode.cn id=148 lang=java
 *
 * [148] 排序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode right = slow.next;
        slow.next=null;
        ListNode left = head;
 
        return merge(sortList(left),sortList(right));
    }

    private ListNode merge(ListNode list1, ListNode list2){
       ListNode head = new ListNode(-1);
       ListNode dummy = head;
       while(list1!=null && list2!=null){
           if(list1.val<list2.val){
               dummy.next = list1;
               list1=list1.next;
           }else{
               dummy.next=list2;
               list2=list2.next;
           }
          dummy=dummy.next;
       }

        if(list1!=null){
            dummy.next=list1;
        }

        if(list2!=null){
            dummy.next=list2;
        }

        return head.next;
    }


}
// @lc code=end