Update 143.Reorder-List.cpp

wisdompeak · web-flow · commit 0547f99227c4 · 2021-11-21T15:42:41.000-08:00
diff --git a/Linked_List/143.Reorder-List/143.Reorder-List.cpp b/Linked_List/143.Reorder-List/143.Reorder-List.cpp
@@ -3,57 +3,65 @@
  * struct ListNode {
  *     int val;
  *     ListNode *next;
- *     ListNode(int x) : val(x), next(NULL) {}
+ *     ListNode() : val(0), next(nullptr) {}
+ *     ListNode(int x) : val(x), next(nullptr) {}
+ *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  * };
  */
 class Solution {
 public:
     void reorderList(ListNode* head) 
     {
-        if (head==NULL || head->next==NULL)
-            return;
-        
-        ListNode* h=new ListNode(0);
-        h->next=head;
-        
-        ListNode* p=h;
-        int count=0;
-        while (p->next!=NULL)
+        ListNode* dummy = new ListNode(0);
+        dummy->next = head;
+
+        ListNode* p = dummy;
+        int count = 0;
+        while (p->next)
         {
-            p=p->next;
             count++;
-        }        
-        p=h;
-        for (int i=0; i<(count-count/2); i++)
-            p=p->next;       
-                                      
-        ListNode* temp=p->next;
-        p->next=NULL;
-        p=temp;
-        ListNode* q=NULL;
-        while (p!=NULL)
-        {
-            ListNode* temp=p->next;
-            p->next=q;
-            q=p;
-            p=temp;
+            p = p->next;
         }
-        
-        p=head;        
-        while (p!=NULL || q!=NULL)
+
+        ListNode* q = dummy;
+        for (int i=0; i<(count+1)/2; i++)
+            q = q->next;
+        ListNode* head2 = q->next;
+        q->next = NULL;
+
+        head2 = reverseLinkedList(head2);
+
+        p = head, q = head2;
+        ListNode* h = dummy;
+        while (p || q)
         {
-            if (p!=NULL)
+            if (p)
             {
-                h->next=p;
-                h=h->next;
-                p=p->next;
+                h->next = p;
+                p = p->next;
+                h = h->next;
             }
-            if (q!=NULL)
+            if (q)
             {
-                h->next=q;
-                h=h->next;
-                q=q->next;
+                h->next = q;
+                q = q->next;
+                h = h->next;
             }
-        }        
+        }
+    }
+
+    ListNode* reverseLinkedList(ListNode* head)
+    {
+        ListNode* cur = head;
+        ListNode* last = NULL;
+        ListNode* next = NULL;
+        while (cur!=NULL)
+        {
+            next = cur->next;
+            cur->next = last;
+            last = cur;
+            cur = next;
+        }
+        return last;
     }
 };
