Frontend School

Rearrange Linked List by Parity

DSA
medium

Rearrange Linked List by Parity

Medium
Linked List
Pointers

Overview

In healthcare data systems, linked lists are sometimes used to represent sequences of records, such as patient visits or medication events. For certain analytical tasks, it can be beneficial to reorder these sequences based on specific criteria to optimize processing or improve data locality. This problem challenges you to efficiently rearrange a linked list by separating nodes based on their original index parity.

What you need to do / Task

You are given the head of a singly linked list. Your task is to rearrange the list such that all nodes at odd indices appear before all nodes at even indices. The relative order of nodes within the odd group and within the even group must be preserved. The first node is considered to be at index 0 (an odd index for the purpose of this problem, as it's the 1st node).

For example: If the input list is 1 -> 2 -> 3 -> 4 -> 5

  • Odd-indexed nodes (0, 2, 4, ...): 1, 3, 5
  • Even-indexed nodes (1, 3, 5, ...): 2, 4 The rearranged list should be 1 -> 3 -> 5 -> 2 -> 4.

Input & output

  • Input: head: A ListNode representing the head of a singly linked list.
  • Output: A ListNode representing the head of the rearranged linked list.

Clarifications

  • The problem refers to "odd-indexed" and "even-indexed" based on a 0-based index. So, the 1st node (index 0) is considered "odd-indexed", the 2nd node (index 1) is "even-indexed", the 3rd node (index 2) is "odd-indexed", and so on.
  • The list can be empty or contain only one node.
  • The number of nodes in the list will not exceed 10^4.

Examples

1

Example 1

Input:

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

Output:

[1,3,5,2,4]

Note:

Original list: 1 (idx 0) -> 2 (idx 1) -> 3 (idx 2) -> 4 (idx 3) -> 5 (idx 4). Odd-indexed nodes: 1, 3, 5. Even-indexed nodes: 2, 4. Rearranged: 1 -> 3 -> 5 -> 2 -> 4.

2

Example 2

Input:

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

Output:

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

Note:

Original list: 2 (idx 0) -> 1 (idx 1) -> 3 (idx 2) -> 5 (idx 3) -> 6 (idx 4) -> 4 (idx 5) -> 7 (idx 6). Odd-indexed nodes: 2, 3, 6, 7. Even-indexed nodes: 1, 5, 4. Rearranged: 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4.

3

Example 3

Input:

head = [1,2,3]

Output:

[1,3,2]

Note:

Original list: 1 (idx 0) -> 2 (idx 1) -> 3 (idx 2). Odd-indexed nodes: 1, 3. Even-indexed nodes: 2. Rearranged: 1 -> 3 -> 2.

Constraints

Constraints & assumptions

  • The number of nodes in the linked list will be in the range [0, 10^4].
  • Node values will be integers in the range [-10^6, 10^6].
  • Your solution should operate in O(1) space complexity.
  • Your solution should operate in O(N) time complexity, where N is the number of nodes in the list.

What interviewers evaluate

  • Correctness: Does the solution correctly rearrange the linked list for all valid inputs, including edge cases?
  • Efficiency: Is the solution optimized for time and space complexity as per the constraints?
  • Code Structure & Readability: Is the code well-organized, clean, and easy to understand? Are variable names descriptive?
  • Pointer Manipulation: Demonstrates a solid understanding of linked list pointer operations without errors or off-by-one issues.

Loading editor...