# Sort List

## Sort List

Question

[Leetcode: Sort List | LeetCode OJ](https://leetcode.com/problems/sort-list/)\
[Lintcode: (98) Sort List](http://www.lintcode.com/en/problem/sort-list/)

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

## 题解思路

链表的排序操作，对于常用的排序算法，能达到O(nlogn)的复杂度有快速排序(平均情况)，归并排序，堆排序。

对于数组，归并排序一般需要使用O(n)的额外空间，虽然也有原地的实现方法。但对于链表这样的数据结构，排序是指针next值的变化，所以只需要常数级的额外空间。

归并排序的核心思想在于，根据分治思想，可以按照左、右、合并的顺序，实现递归模型，也就是先找出左右链表，最后进行归并。

**三个主要步骤**

1. **找到链表中点**：可以通过快慢指针的方法
2. **合并两个有序链表**：链表的基本问题
3. **分治递归**

## 源代码

```java
/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */

public class Solution {
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode pointer = dummy;

        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                pointer.next = head1;
                head1 = head1.next;
            } else {
                pointer.next = head2;
                head2 = head2.next;
            }
            pointer = pointer.next;
        }

        if (head1 != null) {
            pointer.next = head1;
        } else {
            pointer.next = head2;
        }

        return dummy.next;
    }

    /**
     * @param head: The head of linked list.
     * @return: You should return the head of the sorted linked list,
                    using constant space complexity.
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode mid = findMiddle(head);
        ListNode right = sortList(mid.next);
        mid.next = null;
        ListNode left = sortList(head);

        return merge(left, right);
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/linked_list/sort_list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.