my c++ easy to understand solution


  • 0
    D
    class Solution {
    public:
        ListNode *findPrevMid(ListNode *head) {
            ListNode *slow = head, *fast = head;
            while(fast && fast -> next && fast -> next -> next) {
                slow = slow -> next;
                fast = fast -> next -> next;
            }
            return slow;
        }
        ListNode *reverse(ListNode *head) {
            if(!head || !head -> next) return head;
            ListNode *sub = reverse(head -> next);
            head -> next -> next = head;
            head -> next = nullptr;
            return sub;
        }
        void reorderList(ListNode* head) {
            if(!head || !head -> next) return;
            ListNode *mid_prev = findPrevMid(head);
            ListNode *mid = mid_prev -> next;
            mid_prev -> next = nullptr;  
            ListNode *l1 = head, *l2 = reverse(mid);
            while(l1 && l2) {
                ListNode *tmp1 = l1 -> next, *tmp2 = l2 -> next;
                l1 -> next = l2;
                l2 -> next = tmp1;
                l1 = tmp1;
                l2 = tmp2;
            }
        }
    };
    

Log in to reply
 

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