leetcode-148. 排序链表

标题形貌
给你链表的头结点 head ，请将其按 升序 分列并返回 排序后的链表 。

示例 1：

2. <strong>输入：</strong>head = [4,2,1,3]
3. <strong>输出：</strong>[1,2,3,4]

复制代码

示例 2：

2. <strong>输入：</strong>head = [-1,5,3,4,0]
3. <strong>输出：</strong>[-1,0,3,4,5]

复制代码

示例 3：

2. <strong>输入：</strong>head = []
3. <strong>输出：</strong>[]

复制代码

思绪
使用快慢指针完成+归并两个有序链表完成归并排序

2. # Definition for singly-linked list.
3. class ListNode(object):
4.     def __init__(self, val=0, next=None):
5.         self.val = val
6.         self.next = next
7. class Solution(object):
8.     def sortFunc(self, head, tail):
9.         if not head:
10.             return head
11.         if head.next == tail:
12.             head.next = None
13.             return head
14.         slow = fast = head
15.         while fast != tail:
16.             slow = slow.next
17.             fast = fast.next
18.             if fast != tail:
19.                 fast = fast.next
20.         mid = slow
21.         return self.merge(self.sortFunc(head, mid), self.sortFunc(mid, tail))
23.     def merge(self, head1, head2):
24.         pre = ListNode(-1)
25.         head, head1, head2 = pre, head1, head2
26.         while head1 and head2:
27.             if head1.val <= head2.val:
28.                 head.next = head1
29.                 head1 = head1.next
30.             else:
31.                 head.next = head2
32.                 head2 = head2.next
33.             head = head.next
34.         if head1:
35.             head.next = head1
36.         if head2:
37.             head.next = head2
38.         return pre.next
40.     def sortList(self, head):
41.         """
42.         :type head: ListNode
43.         :rtype: ListNode
44.         """
45.         return self.sortFunc(head, None)
47. if __name__ == '__main__':
48.     s = Solution()
49.     head = ListNode(1)
50.     phead = head
51.     data = [4, 3, 7, 5]
52.     for i in data:
53.         node = ListNode(i)
54.         phead.next = node
55.         phead = phead.next
56.     head = s.sortList(head)
57.     while head:
58.         print(head.val),
59.         head = head.next

复制代码

二刷：

2. # Definition for singly-linked list.
3. # class ListNode(object):
4. #     def __init__(self, val=0, next=None):
5. #         self.val = val
6. #         self.next = next
7. class Solution(object):
8.     def sortFunc(self,head, tail):
9.         if not head:
10.             return None
11.         if head.next == tail:
12.             head.next = None
13.             return head
14.         slow = fast = head
15.         while fast!=tail:
16.             slow=slow.next
17.             fast = fast.next
18.             if fast!=tail:
19.                 fast=fast.next
20.         mid = slow
21.         return self.merge(self.sortFunc(head,mid), self.sortFunc(mid,tail))
23.     def merge(self, head1, head2):
24.         pre = ListNode(-1)
25.         head = pre
26.         while head1 and head2:
27.             if head1.val<head2.val:
28.                 head.next = head1
29.                 head1 = head1.next
30.             else:
31.                 head.next = head2
32.                 head2 = head2.next
33.             head = head.next
34.         if head1:
35.             head.next = head1
36.         if head2:
37.             head.next = head2
38.         return pre.next
40.     def sortList(self, head):
41.         """
42.         :type head: Optional[ListNode]
43.         :rtype: Optional[ListNode]
44.         """
45.         return self.sortFunc(head,None)

复制代码

影象点：
快慢指针找中心节点+归并+头尾相连返回none
ps:主函数的入参是:head,None