Why use function can't change the list,and use the function the result is wrong


  • 0
    F

    /**

    • 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) {
      if(head==NULL || head->next == NULL)
      return head;

       //length>=2
       ListNode *p=head;
       ListNode *q=p->next;
      
       while(q)
       {
            //q的值小于p时,在head和p(不包含p)之间插入,可能在head之前,也可能在head之后&&p之前插入
            //q的值大于等于p时,直接在p之后插入
             ListNode *p2=head;
             ListNode *q2=p2->next;
             ListNode *tmp=q->next;
            if(head->val >= q->val)         //为新的头结点
            {
                
                head=q;
                head->next=p2;
                q=tmp;
                p->next=q;
                continue;
            }
            else if(q->val >= p->val)     //直接插入到p之后
           {   
               p->next=q;
               q=tmp;
               p=p->next;
               p->next=q;
               continue;
           }
           else{
             p->next=NULL; 
            while(q2 && q2->val < q->val)   
           {    
                p2=p2->next;
                q2=q2->next;
           }
           //在p2,q2之间插入,q2还未到达最后一个节点处
                p2->next=q;
                q->next=q2;
                q=tmp;
                p->next=q;
              
           }
      }
      return head;
      

      }

    private:
    void InsertNode(ListNode *head,ListNode *p,ListNode *q)
    {
    ListNode *p2=head;
    ListNode *q2=p2->next;
    ListNode *tmp2=q->next;

         while(q2 && q2->val < q->val)   
         {    
                 p2=p2->next;
                 q2=q2->next;
         }
           //在p2,q2之间插入,q2还未到达最后一个节点处
                 p2->next=q;
                 q->next=q2;
                 q=tmp2;
                 p->next=q;
                 return ;
         
     }
    

    };


Log in to reply
 

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