SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given a singly linked list, the goal is to reorder the list in such a way that the nodes are arranged in a specific order: the first node, then the last node, followed by the second node, then the second last node, and so on. This should be done in-place without altering the node values.

Intuition

The problem can be intuitively approached by breaking it down into two steps: first, storing the nodes in a list for easy access, and second, reordering the nodes by alternating between the front and the back of the list. The challenge lies in efficiently rearranging the nodes without altering their values.

Approach

1. Storing Nodes:

   • Traverse the linked list and store each node in a list or array. This allows random access to any node, making it easier to rearrange them.

2. Reordering Nodes:

   • Initialize a pointer to the head of the list.
   • Use a loop to reorder the nodes by alternately assigning the next pointer of the current node to the front and then the back of the list/array.
   • Continue this process until all nodes are rearranged.

3. Final Adjustment:

   • Set the next pointer of the last node to null to mark the end of the reordered list.

Complexity

Time Complexity**:

(O(N)), where (N) is the number of nodes in the linked list. This accounts for the traversal of the list to store the nodes and the reordering process.

Space Complexity:

(O(N)), where (N) is the number of nodes. This is due to the extra space used to store the nodes in a list or array.

Code

C++

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head) return;

        std::vector<ListNode*> nodes;
        ListNode* pointer = head;

        while (pointer) {
            nodes.push_back(pointer);
            pointer = pointer->next;
        }

        pointer = head;
        int i = 0;

        while (!nodes.empty()) {
            if (i % 2 == 0) {
                pointer->next = nodes.front();
                nodes.erase(nodes.begin());
            } else {
                pointer->next = nodes.back();
                nodes.pop_back();
            }
            pointer = pointer->next;
            i++;
        }

        pointer->next = nullptr;
    }
};

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head:
            return

        nodes = []
        pointer = head

        while pointer:
            nodes.append(pointer)
            pointer = pointer.next

        pointer = head
        i = 0

        while nodes:
            if i % 2 == 0:
                pointer.next = nodes.pop(0)
            else:
                pointer.next = nodes.pop()

            pointer = pointer.next
            i += 1

        pointer.next = None

Java

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;

        List<ListNode> nodes = new ArrayList<>();
        ListNode pointer = head;

        while (pointer != null) {
            nodes.add(pointer);
            pointer = pointer.next;
        }

        pointer = head;
        int i = 0;

        while (!nodes.isEmpty()) {
            if (i % 2 == 0) {
                pointer.next = nodes.remove(0);
            } else {
                pointer.next = nodes.remove(nodes.size() - 1);
            }
            pointer = pointer.next;
            i++;
        }

        pointer.next = null;
    }
}

JavaScript

var reorderList = function (head, pointer = head, arr = []) {

    for (; pointer; arr.push(pointer), pointer = pointer.next);
    for (i = 0, pointer = head; arr.length; i++, pointer = pointer.next) {
        pointer.next = i % 2 ? arr.pop() : arr.shift();
    }
    pointer.next = null
};