143

143. Reorder List (Medium)

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

 

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

 

Constraints:

• The number of nodes in the list is in the range [1, 5 * 104].
• 1 <= Node.val <= 1000

Companies:
Amazon, Adobe, Bloomberg

Related Topics:
Linked List, Two Pointers, Stack, Recursion

Similar Questions:

• Delete the Middle Node of a Linked List (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/reorder-list/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
    int getLength(ListNode *head) {
        int ans = 0;
        for (; head; head = head->next) ++ans;
        return ans;
    }
    ListNode *splitList(ListNode *head) {
        int len = (getLength(head) - 1) / 2;
        while (len--) head = head->next;
        auto ans = head->next;
        head->next = nullptr;
        return ans;
    }
    ListNode *reverseList(ListNode *head) {
        ListNode dummy;
        while (head) {
            auto node = head;
            head = head->next;
            node->next = dummy.next;
            dummy.next = node;
        }
        return dummy.next;
    }
    void interleave(ListNode *first, ListNode *second) {
        while (second) {
            auto node = second;
            second = second->next;
            node->next = first->next;
            first->next = node;
            first = node->next;
        }
    }
public:
    void reorderList(ListNode* head) {
        auto second = splitList(head);
        second = reverseList(second);
        interleave(head, second);
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/reorder-list/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
    ListNode *splitList(ListNode *head) {
        auto fast = head, slow = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        auto ans = slow->next;
        slow->next = nullptr;
        return ans;
    }
    ListNode *reverseList(ListNode *head) {
        ListNode dummy;
        while (head) {
            auto node = head;
            head = head->next;
            node->next = dummy.next;
            dummy.next = node;
        }
        return dummy.next;
    }
    void interleave(ListNode *first, ListNode *second) {
        ListNode dummy, *tail = &dummy;
        while (first && second) {
            auto node = first;
            first = first->next;
            tail->next = node;
            tail = node;
            node = second;
            second = second->next;
            tail->next = node;
            tail = node;
        }
        tail->next = first;
    }
public:
    void reorderList(ListNode* head) {
        auto second = splitList(head);
        second = reverseList(second);
        interleave(head, second);
    }
};