Solution: divide into two parts, conquer one by one, and them merge two sorted parts.
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: //Merge two sorted linked list ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { if(l1==NULL) return l2; if(l2==NULL) return l1; ListNode* c1 = (l1->val<=l2->val?l1:l2); //pointing to the head with the smaller val ListNode* c2 = (l1->val<=l2->val?l2:l1); //pointing to the head with the larger val while(c1->next!=NULL && c2!=NULL){ if(c1->val<=c2->val && c2->val<=c1->next->val){ //insert c2 behind of c1 ListNode* tmp = c2->next; c2->next = c1->next; c1->next = c2; //advance both pointers c1 = c1->next; c2 = tmp; } else c1 = c1->next; } if(c1->next==NULL) c1->next = c2; return (l1->val<=l2->val?l1:l2); } ListNode *sortList(ListNode *head) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. if(head==NULL || head->next==NULL) return head; //Advance slow pointer to middle node ListNode* slow = head; ListNode* fast = head->next; while(fast!=NULL && fast->next!=NULL){ slow=slow->next; fast=fast->next->next; } ListNode* newHead = slow->next; slow->next=NULL; //Sort two parts head=sortList(head); newHead=sortList(newHead); //Merge two sorted parts return mergeTwoLists(head, newHead); } };
No comments:
Post a Comment