# Sort List

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        Time Complexity: O(n)
        """
        if not head or not head.next:
            return head

        slow = fast = head
        # 切對半 為何先 fast 在 fast.next 不能對調, 因為fast.next
        while fast and fast.next:
            fast = fast.next.next
            pre = slow
            slow = slow.next
        pre.next = None
        
        head2 = slow
        left = self.sortList(head)
        right = self.sortList(head2)
        return self.merge(left, right)

    def merge(self, left, right):
        # 對於 sinlge linked list 的 add 或 delete node 最好有 dummy node 會省事很多
        dummy = node = ListNode(0)

        while left and right:
            if left.val < right.val:
                node.next = left
                left = left.next
            else:
                node.next = right
                right = right.next

            node = node.next
        # if not left return right else return left
        node.next = left or right
        
        return dummy.next
```


---

# 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://zcjian.gitbook.io/project/linked-list/untitled.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.