148. Sort List(重要)

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

用归并排序！

相似的题目147. Insertion Sort Li

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* sortList(ListNode* head) {
    if (head == NULL || head->next == NULL) return head;
    else{
      ListNode* faster = head, *slower = head;
      while (faster->next != NULL&&faster->next->next != NULL){
        faster = faster->next->next;
        slower = slower->next;
      }
      ListNode* head2 = slower->next;
      slower->next = NULL;
      head = sortList(head);
      head2 = sortList(head2);
      return merge(head, head2);
    }
  }

private:
  ListNode* merge(ListNode* head1, ListNode* head2){
    ListNode dummy(0);
    ListNode* head = &dummy;
    while (head1&&head2){
      if (head1->val < head2->val){
        head->next = head1;
        head1 = head1->next;
        head = head->next;
      }
      else{
        head->next = head2;
        head2 = head2->next;
        head = head->next;
      }
    }
    if (head1){
      head->next = head1;
    }
    if (head2){
      head->next = head2;
    }
    return dummy.next;
  }
};