143 Reorder List

Given a singly linked list L:

$$L0\longrightarrow L_1\longrightarrow L_2\longrightarrow ... \longrightarrow L{n-1}\longrightarrow L_n$$
reorder it to:

$$L0\longrightarrow L_n\longrightarrow L_1\longrightarrow L{n-1}\longrightarrow L2 \longrightarrow L{n-2}...$$

For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.

• You must do this in-place without altering the nodes' values.

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if ( head == NULL or head->next == NULL ) return;
        int length = 0;
        ListNode *p = head, *tail, *tail2;
        while ( p != NULL ) {
            p = p->next;
            length += 1;
        }
        tail = head;
        for ( int i = 1; i <= (length+1)/2-1; i++ ) tail = tail->next;
        tail2 = tail->next;
        tail->next = NULL;
        // reverse from p1 to the end
        ListNode *p2 = tail2;
        ListNode *p1 = p2->next;
        while (true) {
            if ( p1 == NULL ) break;
            ListNode *tmpp = p1->next;
            p1->next = p2;
            p2 = p1;
            p1 = tmpp;
        }
        tail2->next = NULL;
        // merge p1 to tail, and p2 to tail2
        p1 = head;
        ListNode *dummy = new ListNode(0);
        ListNode *ptail = dummy;
        while ( p1 != NULL or p2 != NULL) {
            if ( p1 != NULL ) {
                ptail->next = p1;
                ptail = ptail->next;
                p1 = p1->next;
            }
            if ( p2 != NULL ) {
                ptail->next = p2;
                ptail = ptail->next;
                p2 = p2->next;
            }
        }
    }
};

Notes
Reverse the second half of the linked list. Merge the first half and the reversed second half.

• DETAILS!

Recursive solution, TLE

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        // 1234->1423
        // 12345->15243
        if ( head == NULL or head->next == NULL or head->next->next == NULL ) return;
        ListNode *p = head;
        while ( p->next->next != NULL ) {
            p = p->next;
        }
        ListNode *next_head = head->next, *tail = p->next;
        p->next = NULL;
        head->next = tail;
        reorderList(next_head);
        tail->next = next_head;
        return;
    }
};