1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
|
struct Node int val; Node* next; Node(int x):val(x),next(NULL){} };
void splitList(Node* head, Node** front, Node** back){ Node *fast, *slow; slow = head; fast = head->next; while(fast != NULL){ fast = fast->next; if(fast != NULL){ fast = fast->next; slow = slow->next; } } *front = head; *back = slow->next; slow->next = NULL; }
Node* sortedMerge(Node* a, Node* b){ if(a == NULL) return b; if(b == NULL) return a; Node* mergedNode; if(a->val <= b->val){ mergedNode = new Node(a->val); mergedNode->next = sortedMerge(a->next, b); }else { mergedNode = new Node(b->val); mergedNode->next = sortedMerge(a, b->next); } return mergedNode; }
void mergeSort(Node** headRef){ Node* head = *headRef; Node* a; Node* b; if(head == NULL || head->next == NULL) return; splitList(head, &a, &b); mergeSort(&a); mergeSort(&b); *headRef = sortedMerge(a, b); }
|
近期评论