leetcode/src/Insertion_Sort_List.cpp at master · zyx4843/leetcode · GitHub

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
54
55
56
57
58
59
60
61
62
63
// Source : https://oj.leetcode.com/problems/insertion-sort-list/
// Author : zheng yi xiong
// Date   : 2014-11-21

/**********************************************************************************
*
* Sort a linked list using insertion sort.
*
**********************************************************************************/

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if ( (NULL == head) || (NULL == head->next) )
		{
			return head;
		}

        ListNode *pSortHead = head;
		ListNode *pSortTail = head;
		ListNode *pPos = head->next;
		ListNode *pTemp = NULL, *pSortPos = NULL;

		while (NULL != pPos)
		{
			if (pPos->val < pSortHead->val)
			{
				pTemp = pSortHead;
				pSortHead = pPos;
				pPos = pPos->next;
				pSortHead->next = pTemp;
			}
			else if (pPos->val >= pSortTail->val)
			{
				pSortTail->next = pPos;
				pSortTail = pPos;
				pPos = pPos->next;
			}
			else
			{
				pSortPos = pSortHead;
				while ( (pSortPos->next != pSortTail) && (pSortPos->next->val < pPos->val) )
				{
					pSortPos = pSortPos->next;
				}

				pTemp = pSortPos->next;
				pSortPos->next = pPos;
				pPos = pPos->next;
				pSortPos->next->next = pTemp;
			}
		}

		pSortTail->next = NULL;
		return pSortHead;
    }
};