LeetCode: Insertion Sort List

leetcode Insertion Sort List Problem Description:

Sort a linked list using insertion sort.

leetcode Insertion Sort List Solution and Source Code:

I have two different ideas to tackle this problem:

(1) The most common method, just apply normal Insertion Sort to the input linked list, this is a good problem to check and test your coding skills of pointer manipulation. Linked list is quite suitable for insertion sort because it only needs constant time O(1) time to insert a node into the sorted list. I think following these THREE steps to implement the Insertion Sort could be less error-prone:  a) cut off the current node from the not sorted part of the list; b) find the right place in the sorted part to insert the cut off node; c) do insertion, take good care of the possible new head of the sorted list part; The following is the accepted source code:

class Solution {
public:
	ListNode *findPositionToInsert(ListNode *head, int val) {
		if (NULL == head) return NULL;
		if (val <= head->val) return NULL;

		ListNode *pCurrentNode  = head->next;
		ListNode *pPreviousNode = head;
		while (NULL != pCurrentNode && pCurrentNode->val < val) {
			pPreviousNode = pCurrentNode;
			pCurrentNode = pCurrentNode->next;
		}
		return pPreviousNode;
	}
	ListNode *insertionSortList_Pointer_Manupilate(ListNode *head) {
		if (NULL == head) return NULL;

		ListNode *pNewHead = head;
		ListNode *pPositionToInsert = NULL;
		ListNode *pTmepNode = NULL;
		ListNode *pCurrentNodeToBeInserted = head->next;
		head->next = NULL;
		while (pCurrentNodeToBeInserted) {
			pTmepNode = pCurrentNodeToBeInserted->next;
			pCurrentNodeToBeInserted->next = NULL;
			pPositionToInsert = findPositionToInsert(pNewHead, pCurrentNodeToBeInserted->val);
			if (NULL == pPositionToInsert) {
				pCurrentNodeToBeInserted->next = pNewHead;
				pNewHead = pCurrentNodeToBeInserted;
			}
			else {
				pCurrentNodeToBeInserted->next = pPositionToInsert->next;
				pPositionToInsert->next = pCurrentNodeToBeInserted;
			}
			pCurrentNodeToBeInserted = pTmepNode;
		}
		return pNewHead;
	}

    ListNode *insertionSortList(ListNode *head) {
		return insertionSortList_Pointer_Manupilate(head);
    }
};

(2) Another method in my mind is like this: a) one pass to copy all the data into a temporary vector; b) use swap to do insertion sort on the temporary vector, i.e., normal common insertion sort on an array; c) coy the sorted data in the temporary vector into the original List.

This one does not involve pointer manipulate and surely is less error-prone, but this might not be the point of this problem.

leetcode Insertion Sort List Tips and Remarks:

Firstly, note by cutting off the current node from the not sorted part of the linked list in the step a) of method (1), I mean, we need to set the next pointer of the cut off node to be NULL, this is quite a good trick so that you don’t have to handle the Tail of the sorted list part explicitly. Review the source code carefully and you will find it (cutting off) quite useful.

Secondly, don’t mix the sorted list and the unsorted list together, say the sorted list is A and the other is B, remember, A and B are not linked at all, and one useful & less error-prone action to take is just cutting of the first node from b and then insert into A.

Written on July 26, 2014