18-line 3-step clean & easy-understand c++


  • 1
    M
    class Solution {
    public:
    
        void reorderList(ListNode* head) {
            // count node number
            int n=0;
            ListNode *t=head;
            while (t) t=t->next, n++;
            if (n<=2) return;
                
            // reverse the second half
            int m=(n+3)/2 - 1;
            t=head;
            while (m) t=t->next, m--;
            t=reverse(t);
            
            // merge
            ListNode *t2=t->next;
            while (t) {
                t->next=head->next, head->next=t, head=t->next;
                t=t2, t2= t ? t->next : NULL;
            }
            if (head) head->next = NULL;
        }
    
        ListNode *reverse(ListNode *r) {
            if (r && r->next) {
                ListNode *n=r->next, *nn=r->next->next;
                r->next=0;
                while (n) n->next=r, r=n, n=nn, nn= n ? n->next : NULL;
            }
            return r;
        }
    };

Log in to reply
 

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