# Wrong answer, Input:{3,2,1} Output:{1,3,2} Expected:{1,2,3}

• I wrote code as below, and I tested on VS, it could work. But OJ always reminds me that it is wrong answer, any help?

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.

ListNode* pNodePre = NULL;
ListNode* pNodeNext = NULL;

while(pNodeIndex)
{
ListNode* pCompareIndexPre = NULL;
pNodeNext = pNodeIndex->next;
bool bPosChanged = false;
while(pCompareIndex < pNodeIndex)
{
if(pCompareIndex->val > pNodeIndex->val)
{
if(pCompareIndexPre)
pCompareIndexPre->next = pNodeIndex;
pNodeIndex->next = pCompareIndex;

if(pNodePre)
pNodePre->next = pNodeNext;
bPosChanged = true;
break;
}

pCompareIndexPre = pCompareIndex;
pCompareIndex = pCompareIndex->next;
}

if(!bPosChanged)
pNodePre = pNodeIndex;
pNodeIndex = pNodeNext;
}

}
};``````

• Hi ArronLin:
this is my code:

``````public ListNode insertionSortList(ListNode head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
{
}
ListNode cur, pre, next, node;   //sequence is like this: pre-next-...-cur-node
while(cur!= null)
{
node = cur.next;              //save next node of cur
{
}
else
{
while(next!= null && next.val<cur.val)   //if cur.val larger than next.val, pre++ and next++ (move to next)
{
pre = next;
next = next.next;
}
cur.next = next;                       //insert cur
pre.next = cur;
}
cur = node;                               //cur++   :move to next node
}

}
``````

• Thank you, yuxi0203; I finally found that my fault is using below sentence of code:
"while(pCompareIndex < pNodeIndex)"
It is not right to compare the pointer of two link list node to determine their sequence.

• My solution with a dummy head:

``````ListNode *insertionSortList(ListNode *head) {
ListNode dummy = ListNode(INT_MIN);

ListNode *cur = &dummy;
ListNode *sorted = &dummy;

while (cur)
{
// store the currently sorted end
if (cur->val >= sorted->val)
{
// if it's already greater than or equal
// just advance to the next one
// also update the sorted pointer
sorted = cur;
cur = cur->next;
}
else
{
// otherwise start insertion sort
ListNode *tmp = &dummy;
while (tmp->next && tmp->next->val < cur->val)
{
tmp = tmp->next;
}

// Now tmp is the last node less than the cur
//
// dummy, ..., tmp, tmp->next, ..., sorted, cur, cur->next, ...
//
// we want it to become:
//
// dummy, ..., tmp, cur, tmp->next, ..., sorted, cur->next, ...
//
ListNode *tmpNxt = tmp->next;
ListNode *curNxt = cur->next;

tmp->next = cur;
cur->next = tmpNxt;
sorted->next = curNxt;

sorted = cur;
cur = cur->next;
}
}

return dummy.next;
}``````

• thx for discussion. Just one advice about your code: If possible, try to write some comments on your code, that might helpful for others to read when finding errors and bugs. Although I know my comments are not clear, I will try to explain more clear next time. :) GoodLuck

• dummy does a pretty wonderful job on this task, make code more clear than normal.

• memory leak detected

• Thanks @wangya. Just changed the dummy to a ListNode struct.

• hi yuxi0203, I don't think your solution follows the concept of insertion sorting. Since at each time, you first compare the current node to the head. However, based on the insertion sort, the current node should first compare with its previous node.
For example, 1=>2=>3=>-1=>0, the -1 should first compare with 3, and then 2, and finally 1.

• Well, it depends how you think.
For the concept of insertion sort, you are right, but remember that is base on array, you can use index of array to simply find the previous nodes.
However, for single linked list (not double linked list), there is no "parent" pointer, all you have are only "value" and "next" attributes. You have to start from beginning.
For your instance. how can you find 3 if you don't start from 1? if you stick to convention, , you have to search one by one until find the previous node, so on so forth. Time complexity is O(n!) for only one node comparison. It's not necessary to spend time on searching

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.