147 Insertion Sort List

Sort a linked list using insertion sort.

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode *dummy = new ListNode(INT_MIN);
        ListNode *p1 = head;
        while ( p1 != NULL ) {
            ListNode *p2 = dummy, *next_p1 = p1->next;
            while ( true ) {
                if ( p2->next == NULL or p2->next->val > p1->val ) {
                    ListNode *tmpp = p2->next;
                    p2->next = p1;
                    p1->next = tmpp;
                    break;
                }
                else p2 = p2->next;
            }
            p1 = next_p1;
        }
        return dummy->next;
    }
};

Notes:
Two loops:

• First loop to traverse the unsorted linked list.
• Second loop to traverse the sorted linked list until the appropriate insertion place is found.