My Accepted Code


  • 0
    F
    ListNode *reverseList(ListNode *head) {
        ListNode *p = head;
        ListNode *prev = NULL, *tmp;
        while (p) {
            tmp = p->next;
            p->next = prev;
            prev = p;
            p = tmp;
        }
        return prev;
    }
    
    ListNode *merge(ListNode *first, ListNode *second) {
        
        if (!first || !second) return first ? first : second;
        ListNode dummy(0);
        ListNode *node = &dummy;
        while (second) { //note: second finish firstly because: length(second) <= length(second);
            node->next = first;
            first = first->next;
            node = node->next;
            node->next = second;
            second = second->next;
            node = node->next;
        }
        node->next = first;
        return node->next;
    }
    
    ListNode *reorderList(ListNode *head) {
        if (!head || !head->next) return head;
        ListNode *slow = head, *fast = head;
        while (fast != NULL && fast->next != NULL && fast->next->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode *first = head;
        //length(second) <= length(second);
        ListNode *second = reverseList(slow->next);
        slow->next = NULL;
        merge(first, second);
        return head;
    }

Log in to reply
 

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