Reorder List such that i-th element points to n-i-th element

Problem

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 → L1 → L_{n - 1} → L2 → L_{n - 2} → …

Examples

Example 1:

---
title: Input List
---
graph LR
	A1[1] --> B2[2] --> C3[3] --> D4[4]

---
title: Output
---
 graph LR
   A1[1] --> D4[4] --> B2[2] --> C3[3]

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

Example 2:

graph TB
 classDef darkMode fill:transparent,stroke:#ff8c00,stroke-width:2px,font-weight:bold,font-size:14px;
 
 classDef green fill:transparent,stroke:#00ff8c,stroke-width:2px,font-weight:bold,font-size:14px;

    subgraph Original[" "]
	 L1(1):::darkMode --> L2(2):::darkMode --> L3(3):::darkMode --> L4(4):::darkMode --> L5(5):::darkMode
    end
    
    
    subgraph After[" "]
        A2(1):::green
        B2(5):::green
        C2(2):::green
        D2(4):::green
        E2(3):::green

        A2 --> B2 --> C2 --> D2 --> E2
    end
    
    Original -->|Reorder| After
    
linkStyle 0,1,2,3 stroke:#ff8c00,stroke-width:4px,color:red; 
linkStyle 4,5,6,7 stroke:#00ff8c,stroke-width:4px,color:green; 
linkStyle 8 stroke:navyblue,stroke-width:4px,color:navy;

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 * 10^4].
1 <= Node.val <= 1000

Solution

This problem is not straightforward, because it requires "in-place" operations. That means we can only change their pointers, not creating a new list.

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Break the List and Reverse Second Half

This problem can be solved by following these steps:

Break the list in the middle into two halves using fast and slow pointers.
Reverse the second half of the list.
Merge the two halves back together.

For example, given the input list:

1->2->3->4->5->6->7->8
After breaking: List A: 1->2->3->4 and List B: 5->6->7->8
Reverse List B: 8->7->6->5
Merge them into: 1->8->2->7->3->6->4->5

The method works for both even and odd-length lists. For instance, if the list has an odd number of nodes, such as 5, the first part will have 3 nodes and the second part will have 2 nodes, and the solution will still be valid.

There is no need to return anything since we perform the operations in place.

Code

Java

class Solution {
    public void reorderList(ListNode head) {
		if (head == null || head.next == null || head.next.next == null) {
			return;
		}
	
		ListNode middle = getMidNode(head);
		ListNode second = middle.next;
	
		middle.next = null; // split the list
	
		second = reverseIterative(second);
	
		ListNode first = head;
	
		ListNode curr1 = first;
		ListNode curr2 = second;
	
		// second will be equal or less than first in length
		// so iterate on curr2
		while (curr2 != null) {
			ListNode temp1 = curr1.next;
			ListNode temp2 = curr2.next;
	
			curr1.next = curr2;
			curr2.next = temp1;
	
			curr1 = temp1;
			curr2 = temp2;
		}        
    }
	public ListNode getMidNode(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode slow = head;
		ListNode fast = head;
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}
	
	public ListNode reverseIterative(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode prev = null;
		ListNode curr = head;
		while (curr != null) {
			ListNode next = curr.next;
			curr.next = prev;
			prev = curr;
			curr = next;
		}
		return prev;
	}    
}

Complexity

⏰ Time complexity: O(n), where n is the number of nodes in the linked list. Here's the breakdown:
- Finding the middle node: O(n)
- Reversing the second half: O(n)
- Merging the two halves: O(n)
🧺 Space complexity: O(1), since we only use a constant amount of extra space for the pointers and variables.