Frontend School

Interleave Linked List Halves

DSA
medium

Interleave Linked List Halves

Medium
Linked List
Two Pointers
In-place

Overview

In many data processing scenarios, especially those involving sequential data or queues, there's a need to rearrange elements to optimize access patterns or for specific display requirements. This problem challenges you to efficiently interleave the nodes of a singly linked list, combining its first and second halves in an alternating fashion. Mastery of in-place linked list manipulations is crucial for building high-performance systems.

What you need to do / Task

Given the head of a singly linked list, rearrange it such that nodes from the first half and the second half are interleaved. The rearrangement must be performed in-place, modifying the original list structure. You should return the head of the modified list.

Specifically, your task involves the following steps:

  1. Find the middle of the linked list. If the list has an odd number of nodes, the first half should contain the middle node.
  2. Split the list into two separate halves at the middle point.
  3. Reverse the second half of the linked list.
  4. Merge the two halves alternately. The merging should start with a node from the first half, then a node from the reversed second half, then the next node from the first half, and so on. If one half runs out of nodes, append the remaining nodes of the other half.

Input & output

Input:

  • head: ListNode | null - The head of a singly linked list. Each ListNode has an integer val and a next pointer to the next node.

Output:

  • ListNode | null - The head of the rearranged linked list.

Clarifications

  • Empty list: If the input head is null, return null.
  • Single node list: If the list contains only one node, it remains unchanged. Return the original head.
  • In-place modification: You must modify the existing list nodes. Do not create new nodes or use auxiliary data structures that store all node values (aim for O(1) auxiliary space).

Examples

1

Example 1

Input:

head = [1,2,3,4,5,6]

Output:

[1,6,2,5,3,4]

Note:

The list is split into [1,2,3] and [4,5,6]. The second half is reversed to [6,5,4]. Then, they are interleaved: 1 from first, 6 from second, 2 from first, 5 from second, 3 from first, and 4 from second.

2

Example 2

Input:

head = [1,2,3,4,5]

Output:

[1,5,2,4,3]

Note:

The list is split into [1,2,3] (first half with middle node) and [4,5]. The second half is reversed to [5,4]. Then, they are interleaved: 1 from first, 5 from second, 2 from first, 4 from second, and finally 3 from the remaining first half.

3

Example 3

Input:

head = [1,2]

Output:

[1,2]

Note:

For a two-node list, the first half is [1] and the second is [2]. Reversing the second half gives [2]. Interleaving yields [1,2], which is effectively no change but demonstrates the logic for small lists.

Constraints

Constraints & assumptions

  • 0 <= Number of nodes <= 5 * 10^4
  • 1 <= Node.val <= 1000
  • The list is a singly linked list.
  • Expected time complexity: O(N), where N is the number of nodes in the list.
  • Expected auxiliary space complexity: O(1).

Out of scope

  • Handling non-integer Node.val values.
  • Dealing with circular or doubly linked lists.
  • Input validation beyond basic null check.

What interviewers evaluate

  • Correct application of linked list traversal techniques (e.g., fast/slow pointers).
  • Proficiency in modifying linked list pointers for splitting, reversing, and merging segments.
  • Ability to manage edge cases and small list sizes gracefully.
  • Adherence to optimal time and space complexity requirements.

Loading editor...