143. Reorder List#

Difficulty: Medium

Link to Problem: To see the Reorder List problem on LeetCode, click here!

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

\(L_0 → L_1 → … → L_{n - 1} → L_n\)

Reorder the list to be on the following form:

\(L_0 → L_n → L_1 → L_{n - 1} → L_2 → L_{n - 2} → …\)

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

Constraints:

  • The number of nodes in the list is in the range \([1, 5 * 10^4]\).

  • 1 <= Node.val <= 1000

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

def reorderList(head):
    if not head or not head.next:
        return head

    # Step 1: Find the middle of the linked list
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # Split the list into two halves
    first_half = head
    second_half = slow.next
    slow.next = None

    # Step 2: Reverse the second half of the linked list
    prev = None
    current = second_half
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    second_half = prev

    # Step 3: Merge the first and reversed second halves alternately
    p1, p2 = first_half, second_half
    while p2:
        next_p1 = p1.next
        next_p2 = p2.next
        p1.next = p2
        p2.next = next_p1
        p1 = next_p1
        p2 = next_p2

    return head

Explanation:#

The reorderList function is designed to reorder a singly linked list following the specific pattern described in the problem statement. Here’s a detailed explanation of how the function works:

  1. Base Cases Handling:

    • The function first checks if the input linked list is empty (not head) or contains only one element (not head.next). If either of these conditions is met, the list cannot be reordered, so the function returns the original list as-is.

  2. Finding the Middle of the Linked List:

    • To reorder the list, we first need to find the middle point so that we can split the list into two halves. This is done using two pointers, slow and fast, initialized to the head of the list.

    • slow moves one step at a time while fast moves two steps at a time. When fast reaches the end of the list or the second-to-last node, slow will be at the middle node.

  3. Splitting the List:

    • After finding the middle node, we split the list into two halves:

      • The first half, first_half, contains nodes from the beginning up to the middle.

      • The second half, second_half, contains nodes from the middle to the end.

    • To split the list, we set the next pointer of the node before the middle node to None.

  4. Reversing the Second Half:

    • We reverse the second half of the linked list using the prev, current, and next_node pointers.

    • prev is initially None, and we iterate through the second half. For each node, we:

      • Set the next of the current node to prev, effectively reversing the next pointer direction.

      • Update prev to the current node.

      • Move to the next node using the next_node.

  5. Merging the Two Halves Alternately:

    • We now have two linked lists: first_half and the reversed second_half.

    • We merge these two lists alternately by adjusting the next pointers of the nodes.

    • p1 and p2 are pointers to the current nodes in first_half and second_half, respectively.

    • We iterate through both lists while reordering nodes:

      • Set the next of p1 to p2 to link a node from the first half to a node from the reversed second half.

      • Update p1 and p2 to their respective next nodes.

      • Repeat this process until we have processed all nodes in both halves.

  6. Returning the Reordered List:

    • After the merging process is complete, the linked list is reordered as specified.

    • The function returns the head of the reordered list.

The overall result is a singly linked list that has been reordered according to the given pattern. The time complexity of this algorithm is O(N), where N is the number of nodes in the linked list, as we traverse the list once to find the middle, once to reverse the second half, and once to merge the two halves.

# Helper function to print the linked list
def printLinkedList(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

Let’s explain the helper functions: printLinkedList Function:

  • The printLinkedList function takes the head of a linked list as input and returns a list of values representing the nodes in the linked list.

  • Inside the function, a result list is initialized to store the values of the linked list nodes.

  • The function then iterates through the linked list starting from the head node and appends the val attribute of each node to the result list.

  • As it iterates through the list, it moves to the next node using the next attribute of each node.

  • Finally, the function returns the result list containing the values of the linked list nodes in the order they appear in the linked list.

This function is useful for debugging and displaying the contents of a linked list. It allows you to easily convert a linked list into a regular Python list for visualization and testing purposes.

Test cases#

# Example 1
head1 = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
reorderList(head1)
print(printLinkedList(head1))

[1, 4, 2, 3]

# Example 2
head2 = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
reorderList(head2)
print(printLinkedList(head2))

[1, 5, 2, 4, 3]

Let’s analyze the time and space complexity of the reorderList function:

Time Complexity:

  1. Finding the Middle of the Linked List: In this step, we use two pointers, one moving one step at a time (slow) and the other moving two steps at a time (fast). This process takes \(O(N/2)\) time, where \(N\) is the number of nodes in the linked list.

  2. Splitting the List: After finding the middle, we split the list into two halves by setting the next pointer of the node before the middle node to None. This step takes \(O(1)\) time.

  3. Reversing the Second Half: We reverse the second half of the linked list using a while loop that iterates through the second half of the list once. Therefore, this step also takes \(O(N/2)\) time.

  4. Merging the Two Halves Alternately: In this step, we merge the two halves alternately by adjusting the next pointers of the nodes. We iterate through both halves once, so this step takes \(O(N/2)\) time.

Overall, the time complexity of the reorderList function is dominated by the steps involving reversing and merging the two halves, both of which take \(O(N/2)\) time. Therefore, the total time complexity is \(O(N)\).

Space Complexity: The space complexity of the reorderList function is primarily determined by the variables and data structures used within the function. Let’s break down the space complexity components:

  1. Constant Space Variables: The variables slow, fast, prev, current, next_node, p1, and p2 are used to traverse and manipulate the linked list. These variables occupy constant space, regardless of the input size. Therefore, they contribute \(O(1)\) to the space complexity.

  2. Split Linked Lists: In the splitting step, we create two new linked list segments (first_half and second_half) that store references to nodes from the original linked list. These segments occupy space proportional to half of the input list, \(O(N/2)\).

  3. Reversed Second Half: During the reversal step, we reverse the second half of the linked list in-place without creating any additional data structures. Therefore, it doesn’t contribute to additional space complexity.

  4. Overall: Combining the above components, the total space complexity is \(O(N/2)\), which simplifies to \(O(N)\) in terms of space complexity.

In summary, the reorderList function has a time complexity of \(O(N)\) and a space complexity of \(O(N)\) due to the creation of two new linked list segments while splitting the list. The constant space variables used for traversal do not significantly impact the overall space complexity.

Challenging Exercises:#

  1. Reorder by K Elements: Generalize the reorderList function to reorder the list in a different pattern, where you reorder the list by \(K\) elements at a time. For example, for \(K=3\), you would reorder it as (\(L_0 → L_1 → L_2 → L_n → L_{n-1} → L_{n-2} → ...\)). You may need to handle cases where the number of nodes is not a multiple of \(K\).

  2. Reorder by Odd and Even Nodes: Modify the reorderList function to reorder the list in a pattern where odd-indexed nodes (1-based index) come before even-indexed nodes. For example, (\(L_0 → L_n → L_1 → L_{n-1} → L_2 → L_{n-2} → ...\)).