147. Insertion Sort List (Wrong)

// // Created by YUQIONG LI on 17/9/2018. // // to be finished after writing insertion sort for array #include <iostream> using std::cout; using std::endl; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: void printList(ListNode * head){ ListNode * curr = head; while(curr) { cout << curr->val << ' '; curr = curr->next; } cout << endl; } ListNode* insertionSortList(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; ListNode * dummy = new ListNode(0); dummy->next = head; // dummy head just to create a placeholder before head so we can insert before head... ListNode * curr = head->next; // current node to operate upon. At least from the second node ListNode * ptr = dummy; // a pointer to help negative the list until curr. Insert after this ptr. while(curr != nullptr){ cout << "Now operate on node " << curr->val << endl; cout << "Begin shifting pointer."; while((ptr->next->val < curr->val) && (ptr->next != curr)) ptr = ptr->next; // shift the pointer to where the current node should be inserted if (ptr->next != curr){ // Now ptr is the node before insertion. Prepare to swap. cout << "Found insertion position: before node " << ptr->val << endl; // use another pointer prev to find the node before current node ... cout << "Use prev node to find prev node before curr.\n"; ListNode * prev = dummy; while(prev->next != curr) prev = prev->next; // found it! cout << "Prev node found: " << prev->val << endl; cout << "Begin swapping.\n Before swap: "; printList(dummy->next); // swap // take out the current node prev->next = curr->next; // insert the current node into its correct position curr->next = ptr->next; ptr->next = curr; cout << "Swapping finished.\nAfter swap: "; printList(dummy->next); } else { cout << "Did not find insertion position: no need to swap." << endl; cout << "Current position: \n"; printList(dummy->next); } // done. Move on to the next cout << "Done with this node. Move on to the next." << endl; curr = curr->next; } return dummy->next; } }; int main(){ ListNode * head = new ListNode(4); head->next = new ListNode(2); head->next->next = new ListNode(1); head->next->next->next = new ListNode(3); Solution s = Solution(); ListNode * newhead = s.insertionSortList(head); ListNode * ptr = newhead; while (ptr != nullptr){ cout << ptr->val << ' '; ptr = ptr->next; } cout << endl; return 0; }