My accpted C++ code


  • 0
    T
    class Solution {
    public:
        void reorderList(ListNode *head) {
            int len=0,half;
            ListNode *headtmp=head;
            while(head!=NULL)head=head->next,len++;
            head=headtmp; 
            if(len==0||len==1)return;
            half=len/2;   
            ListNode *tmp=head,*p1,*p2,*p3,*pp1,*pp2;
            while(half) {
                if(half==1)p3=tmp;
                tmp=tmp->next;
                half--;
            }
            p3->next=NULL;
            p1=NULL;
            p2=tmp;
            while(p2!=NULL){
                tmp=p2->next;
                p2->next=p1;
                p1=p2;
                p2=tmp;
            }
            p2=p1;
            p1=head;
            while(p1!=NULL&&p2!=NULL) {
                pp1=p1->next;
                pp2=p2->next;
                p1->next=p2;
                if(pp1!=NULL)p2->next=pp1;
                else break;
                p1=pp1;
                p2=pp2;
            }
        }
    };

  • 0
    S

    /**

    • Definition for singly-linked list.

    • struct ListNode {

    • int val;
      
    • ListNode *next;
      
    • ListNode(int x) : val(x), next(NULL) {}
      
    • };
      /
      class Solution {
      public:
      int GetLen(ListNode
      node)
      {
      int n = 0;
      while (node)
      {
      node = node->next;
      n++;
      }
      return n;
      }
      void reorderList(ListNode head) {
      stack<ListNode
      > st;
      queue<ListNode*> q;

       int iLen = GetLen(head);
       
       ListNode* ptemp = head;
       int n = 0;
       while (ptemp)
       {
           if (n >= iLen/2)
               st.push(ptemp);
           else
               q.push(ptemp);
           ptemp = ptemp->next;
           n++;
       }
       
       ListNode* pPrev = NULL;
       ListNode* pRet = NULL;
       while (iLen)
       {
           ListNode* pN1 = NULL; if (q.size()){ pN1 = q.front(); q.pop(); iLen--;}
           ListNode* pN2 = NULL; if (st.size()){pN2= st.top(); st.pop(); iLen--;}
           
           if (pN1)
               pN1->next = pN2;
           else if (pN2)
               pN1 = pN2;
               
           if (pN2)
               pN2->next = NULL;
           
           if (pPrev)
               pPrev->next = pN1;
           else
               pRet = pN1;
           
           pPrev = pN2;
           
       }
       
       head = pRet;
      

      }
      };


Log in to reply
 

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