LeetCode: Reorder List

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…

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

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

---

The approach is that we can reverse the list from middle point to the end first and then connect the the reversed list to the original list one by one. Here is an example:

1 → 2 → 3 → 4 → 5

Reverse from the middle: 1 → 2 → 5 → 4 → 3

Connect the original one to the reversed one: 1 → 5 → 2 → 4 → 3

C++ Code:

/*
 * func: reorder_list
 * goal: reorder the linked list
 * @param head: head node of the list
 * return:
 */
void reorder_list(ListNode *head){
    if(head == nullptr || head->next == nullptr){
        return;
    }
    //Find the middle pointer
    ListNode *slow = head;
    ListNode *fast = head;
    while(fast->next && fast->next->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    
    //Reverse from iter_s->next to the end
    ListNode *prev = slow;
    ListNode *curr = slow->next;
    prev->next = nullptr;
    while(curr) {
        ListNode *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    
    //Reorder
    ListNode *first = head;
    ListNode *second = prev;
    while(first && second && first != second){
        ListNode *tmp = second->next;
        second->next = first->next;
        first->next = second;
        first = second->next;
        second = tmp;
    }
}

Python Code:

# func: reorder the input list
# @param head: head node of the list
# @return:
def reorder_list(head):
    if not head or not head.next:
        return None
    slow = head
    fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    #Reverse from slow to the end
    prev = slow
    curr = slow.next
    prev.next = None
    while curr:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next

    #Reorder
    first = head
    second = prev
    while first and second and first != second:
        next = second.next
        second.next = first.next
        first.next = second

        first = second.next
        second = next

Reference Link:

1. 水中的鱼: [LeetCode] Reorder List, Solution: http://fisherlei.blogspot.com/2013/11/leetcode-reorder-list-solution.html