# [LeetCode] 148. Sort List 链表排序

2021年09月15日 阅读数：1

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

Example 1:java

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

Example 2:node

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

Java:spa

```public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head, pre = head;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;
}
public ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
if (l1 != null) cur.next = l1;
if (l2 != null) cur.next = l2;
return dummy.next;
}
}
```

Java:指针

```public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head, pre = head;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;
}
public ListNode merge(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = merge(l1.next, l2);
return l1;
} else {
l2.next = merge(l1, l2.next);
return l2;
}
}
}
```

Python:orm

```class ListNode:
def __init__(self, x):
self.val = x
self.next = None

def __repr__(self):
if self:
return "{} -> {}".format(self.val, repr(self.next))

class Solution:
# @param head, a ListNode
# @return a ListNode
if head == None or head.next == None:

fast, slow, prev = head, head, None
while fast != None and fast.next != None:
prev, fast, slow = slow, fast.next.next, slow.next
prev.next = None

sorted_l2 = self.sortList(slow)

return self.mergeTwoLists(sorted_l1, sorted_l2)

def mergeTwoLists(self, l1, l2):
dummy = ListNode(0)

cur = dummy
while l1 != None and l2 != None:
if l1.val <= l2.val:
cur.next, cur, l1 = l1, l1, l1.next
else:
cur.next, cur, l2 = l2, l2, l2.next

if l1 != None:
cur.next = l1
if l2 != None:
cur.next = l2

return dummy.next

if __name__ == "__main__":

C++:htm

```class Solution {
public:
ListNode* sortList(ListNode* head) {
ListNode *slow = head, *fast = head, *pre = head;
while (fast && fast->next) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = NULL;
}
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(-1);
ListNode *cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1) cur->next = l1;
if (l2) cur->next = l2;
return dummy->next;
}
};
```

C++:

```class Solution {
public:
ListNode* sortList(ListNode* head) {
ListNode *slow = head, *fast = head, *pre = head;
while (fast && fast->next) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = NULL;
}
ListNode* merge(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
if (l1->val < l2->val) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1, l2->next);
return l2;
}
}
};
```