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


  • 0
    A

    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?

    /**
     * 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) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            if(!head || !head->next)
                return head;
            
            ListNode* pNodeIndex = head;
            ListNode* pNodePre = NULL;
            ListNode* pNodeNext = NULL;
            
            while(pNodeIndex)
            {
                ListNode* pCompareIndex = head;
                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(pCompareIndex == head)
                            head = pNodeIndex;
                        
                        if(pNodePre)
                            pNodePre->next = pNodeNext;
                        bPosChanged = true;
                        break;
                    }
                    
                    pCompareIndexPre = pCompareIndex;
                    pCompareIndex = pCompareIndex->next;
                }
                
                if(!bPosChanged)
                    pNodePre = pNodeIndex;
                pNodeIndex = pNodeNext;
            }
            
            return head;
        }
    };

  • 0
    Y

    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.
                  if(head == null)
                  {
                      return head;
                  }
                  ListNode cur, pre, next, node;   //sequence is like this: pre-next-...-cur-node
                  cur = head.next;
                  head.next = null;
                  while(cur!= null)
                  {
                      node = cur.next;              //save next node of cur
                      if(cur.val<head.val)          //swap when cur is lower than head
                      {
                          cur.next = head;
                          head = cur;
                      }
                      else
                      {
                          pre = head; next = head.next;
                          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
                  }
                  return head;
             
        }
    

  • 0
    A

    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.


  • 0
    C

    My solution with a dummy head:

    ListNode *insertionSortList(ListNode *head) {
        ListNode dummy = ListNode(INT_MIN);
        dummy.next = head;
        
        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;
                
                // advance cur forward
                sorted = cur;
                cur = cur->next;
            }
        }
        
        return dummy.next;
    }

  • 0
    Y

    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


  • 0
    Y

    dummy does a pretty wonderful job on this task, make code more clear than normal.
    Thx for your sharing.


  • 0
    W

    memory leak detected


  • 0
    C

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


  • 0
    C

    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.


  • 0
    Y

    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


Log in to reply
 

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