一：解题思路
Time:O(n*log(n)),Space:O(log(n))
和之前做过的合拼K个链表的第二种方法有点类似，采用归并的思想来做。就是不断的把链表切半，然后递归的处理这2条链表。然后再将这2条排序好的链表合并起来就行。
二：完整代码示例 (C++版和Java版)
C++:
class Solution { private: ListNode* mergeTwoSortedLists(ListNode* l1, ListNode* l2) { ListNode* dummy = new ListNode(0); ListNode* p = dummy; while (l1 != NULL && l2 != NULL) { if (l1->val < l2->val) { p->next = l1; l1 = l1->next; } else { p->next = l2; l2 = l2->next; } p = p->next; } if (l1 != NULL) p->next = l1; if (l2 != NULL) p->next = l2; return dummy->next; } public: ListNode* sortList(ListNode* head) { if (head == NULL || head->next == NULL) return head; ListNode* fast = head; ListNode* slow = head; while (fast->next != NULL && fast->next->next != NULL) { fast = fast->next->next; slow = slow->next; } ListNode* right = sortList(slow->next); slow->next = NULL; ListNode* left = sortList(head); return mergeTwoSortedLists(left,right); } };
Java:
class Solution { private ListNode mergeTwoSortedLists(ListNode l1,ListNode l2) { ListNode dummy=new ListNode(0); ListNode p=dummy; while (l1!=null && l2!=null) { if(l1.val<l2.val) { p.next=l1; l1=l1.next; } else { p.next=l2; l2=l2.next; } p=p.next; } if(l1!=null) p.next=l1; if(l2!=null) p.next=l2; return dummy.next; } public ListNode sortList(ListNode head) { if(head==null || head.next==null) return head; ListNode fast=head; ListNode slow=head; while (fast.next!=null && fast.next.next!=null) { fast=fast.next.next; slow=slow.next; } ListNode right=sortList(slow.next); slow.next=null; ListNode left=sortList(head); return mergeTwoSortedLists(left,right); } }
原文：https://www.cnblogs.com/repinkply/p/12699418.html