Reorder List solution and explanation
Google
Infosys
TCS
9 more videos on this problem
Linkedin Interview Question - Reorder List - Leetcode 143 - PythonNeetCode · 13:47 · 459K views
LeetCode Reorder List Solution Explained - JavaNick White · 12:55 · 35K views
Reorder List (LeetCode 143) | Full Solution with 3 step process and animationsNikhil Lohia · 16:42 · 22K views
Google Coding Interview Question - Reorder List - LeetCode 143AlgoJS · 7:24 · 3K views
Reorder List - LeetCode 143 - Python #reorderlist #leetcode #blind75Deepti Talesra · 13:00 · 3K views
LeetCode 143 | Reorder List | Solution Explained (Whiteboard + Algorithm in Java)Xavier Elon · 7:24 · 2K views
[Java] Leetcode 143. Reorder List [Fast & Slow Pointers #5]Eric Programming · 10:31 · 2K views
reorder list | reorder list leetcode | leetcode 143 | 2 solutions | with stack | reverse second halfNaresh Gupta · 12:34 · 2K views
REORDER LIST | LEETCODE 143 | PYTHON SOLUTIONCracking FAANG · 13:31 · 1K views
Leetcode | 143. Reorder List | Medium | Java SolutionDeveloper Docs · 5:27 · 947 views
The problem
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4] Output: [1,4,2,3]
Example 2:
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 * 104]. 1 <= Node.val <= 1000
Approach overview
Problem Overview: You are given the head of a singly linked list. The goal is to reorder nodes so the list follows the pattern L0 → Ln → L1 → Ln-1 → L2 → Ln-2 .... The structure must be modified in-place without changing node values—only pointers can be rearranged.
Approach 1: Using Array List (O(n) time, O(n) space)
This approach copies all nodes into an array-like structure so you can access both ends easily. First iterate through the linked list and push each node into an ArrayList or dynamic array. Then use two pointers: one starting at the beginning and one at the end. Alternate linking nodes from the front and back while moving the pointers inward. Because random access is O(1), the reordering becomes straightforward. The tradeoff is extra memory proportional to the number of nodes. This approach is simple to reason about and helpful when first understanding pointer rearrangement in a linked list.
Approach 2: Reverse Second Half and Merge (O(n) time, O(1) space)
This is the optimal in-place technique and the one most interviewers expect. First find the middle of the list using the classic slow and fast pointer strategy from two pointers. Once the midpoint is located, reverse the second half of the list. Now you have two lists: the original first half and a reversed second half. Finally merge them by alternating nodes—take one node from the first half, then one from the reversed half, and repeat until the lists are exhausted.
The key insight is that reversing the second half allows you to access the last nodes in forward order without using extra memory. Reversal itself runs in O(n) time and constant space by iteratively updating next pointers. During the merge phase, pointers are carefully rewired so nodes interleave correctly without losing references. This technique relies purely on pointer manipulation and avoids auxiliary structures like a stack or array.
Recommended for interviews: The reverse-and-merge approach is the expected solution because it runs in O(n) time and O(1) extra space. Interviewers often want to see if you can combine multiple linked list techniques: finding the middle, reversing a list, and merging two lists. Starting with the array approach demonstrates the core idea, but implementing the in-place method shows stronger mastery of pointer manipulation.
Approach 1: Reverse Second Half and Merge
This approach involves splitting the list into two halves, reversing the second half, and then merging the two lists alternately.
- Use the slow and fast pointer technique to find the middle of the list.
- Reverse the second half of the list.
- Merge the first half of the list with the reversed second half.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
if not head:
return
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second = slow.next
prev = slow.next = None
while second:
nxt = second.next
second.next = prev
prev = second
second = nxt
first, second = head, prev
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
private ListNode reverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode second = reverseList(slow.next);
slow.next = null;
ListNode first = head;
while (second != null) {
ListNode tmp1 = first.next;
ListNode tmp2 = second.next;
first.next = second;
second.next = tmp1;
first = tmp1;
second = tmp2;
}
}
}#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
while (head) {
ListNode* next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
void reorderList(ListNode* head) {
if (!head || !head->next) return;
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* second = reverseList(slow->next);
slow->next = NULL;
ListNode* first = head;
while (second) {
ListNode* tmp1 = first->next;
ListNode* tmp2 = second->next;
first->next = second;
second->next = tmp1;
first = tmp1;
second = tmp2;
}
}class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
function reorderList(head) {
if (!head || !head.next) return;
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
let second = reverseList(slow.next);
slow.next = null;
let first = head;
while (second) {
let tmp1 = first.next;
let tmp2 = second.next;
first.next = second;
second.next = tmp1;
first = tmp1;
second = tmp2;
}
}
function reverseList(head) {
let prev = null;
while (head) {
let next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode* next;
};
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* current = head;
while (current) {
struct ListNode* next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
void reorderList(struct ListNode* head) {
if (!head || !head->next) return;
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
struct ListNode* second = reverseList(slow->next);
slow->next = NULL;
struct ListNode* first = head;
while (second) {
struct ListNode* tmp1 = first->next;
struct ListNode* tmp2 = second->next;
first->next = second;
second->next = tmp1;
first = tmp1;
second = tmp2;
}
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public void ReorderList(ListNode head) {
if (head == null || head.next == null) return;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode second = Reverse(slow.next);
slow.next = null;
ListNode first = head;
while (second != null) {
ListNode tmp1 = first.next;
ListNode tmp2 = second.next;
first.next = second;
second.next = tmp1;
first = tmp1;
second = tmp2;
}
}
private ListNode Reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}The Python solution employs a clean and concise approach to rearrange the list according to the specified pattern.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 2: Using Array List
This method involves storing the linked list nodes in an array list and then rearranging their connections to achieve the desired order.
- Traverse the linked list and store each node in an array list.
- Use two pointers from start and end of the array to relink the nodes in the desired order.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
if not head:
return
nodes = []
while head:
nodes.append(head)
head = head.next
left, right = 0, len(nodes) - 1
while left < right:
nodes[left].next = nodes[right]
left += 1
if left == right:
break
nodes[right].next = nodes[left]
right -= 1
nodes[left].next = Nonepublic class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
List<ListNode> nodes = new ArrayList<ListNode>();
ListNode node = head;
while (node != null) {
nodes.add(node);
node = node.next;
}
int left = 0;
int right = nodes.size() - 1;
while (left < right) {
nodes.get(left).next = nodes.get(right);
left++;
if (left == right) break;
nodes.get(right).next = nodes.get(left);
right--;
}
nodes.get(left).next = null;
}
}#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
void reorderList(ListNode* head) {
if (!head || !head->next) return;
vector<ListNode*> nodes;
ListNode* node = head;
while (node) {
nodes.push_back(node);
node = node->next;
}
int left = 0, right = nodes.size() - 1;
while (left < right) {
nodes[left]->next = nodes[right];
left++;
if (left == right) break;
nodes[right]->next = nodes[left];
right--;
}
nodes[left]->next = nullptr;
}The Python implementation uses a list to store nodes, then reorders them by alternately connecting nodes from the front and back.
Time Complexity: O(n).
Space Complexity: O(n).
Approach 3: Fast and Slow Pointers + Reverse List + Merge Lists
We first use fast and slow pointers to find the midpoint of the linked list, then reverse the second half of the list, and finally merge the two halves.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
/**
Do not return anything, modify head in-place instead.
*/
function reorderList(head: ListNode | null): void {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
let next = slow.next;
slow.next = null;
while (next) {
[next.next, slow, next] = [slow, next, next.next];
}
let left = head;
let right = slow;
while (right.next) {
const next = left.next;
left.next = right;
right = right.next;
left.next.next = next;
left = left.next.next;
}
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reorderList(head *ListNode) {
fast, slow := head, head
for fast.Next != nil && fast.Next.Next != nil {
slow, fast = slow.Next, fast.Next.Next
}
cur := slow.Next
slow.Next = nil
var pre *ListNode
for cur != nil {
t := cur.Next
cur.Next = pre
pre, cur = cur, t
}
cur = head
for pre != nil {
t := pre.Next
pre.Next = cur.Next
cur.Next = pre
cur, pre = pre.Next, t
}
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
use std::collections::VecDeque;
impl Solution {
pub fn reorder_list(head: &mut Option<Box<ListNode>>) {
let mut tail = &mut head.as_mut().unwrap().next;
let mut head = tail.take();
let mut deque = VecDeque::new();
while head.is_some() {
let next = head.as_mut().unwrap().next.take();
deque.push_back(head);
head = next;
}
let mut flag = false;
while !deque.is_empty() {
*tail = if flag {
deque.pop_front().unwrap()
} else {
deque.pop_back().unwrap()
};
tail = &mut tail.as_mut().unwrap().next;
flag = !flag;
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Reverse Second Half and Merge | Time Complexity: O(n). |
| Using Array List | Time Complexity: O(n). |
| Fast and Slow Pointers + Reverse List + Merge Lists | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Array List | O(n) | O(n) | Simpler implementation when extra memory is acceptable |
| Reverse Second Half and Merge | O(n) | O(1) | Optimal interview solution with constant extra space |
Frequently asked questions
Is Reorder List easy or hard?
Reorder List is generally classified as a medium difficulty problem. The challenge comes from combining multiple linked list operations—finding the midpoint, reversing a list, and merging lists—while carefully maintaining pointer references.
How to solve Reorder List in O(n)?
Find the middle of the list using slow and fast pointers, reverse the second half of the list, then merge the two halves by alternating nodes. Each phase—middle detection, reversal, and merge—takes linear time, resulting in overall O(n) complexity with O(1) extra space.
What is the best approach for Reorder List?
The best approach is reversing the second half of the linked list and then merging it with the first half. This technique uses the slow–fast pointer method to find the middle, reverses the second half in place, and alternates nodes during merge. It runs in O(n) time with O(1) extra space, which is considered the optimal solution.
What data structure is used in Reorder List?
The problem is based on a singly linked list. The optimal solution uses pointer manipulation with techniques such as the two-pointer method and in-place list reversal. Some simpler implementations also use an auxiliary array or stack to access nodes from both ends.
What is the time complexity of Reorder List?
The optimal algorithm runs in O(n) time because the list is traversed a constant number of times: once to find the middle, once to reverse the second half, and once to merge the halves. Each step is linear and does not involve nested iteration.
Reorder List Python or Java solution approach?
Python and Java solutions typically implement the reverse-second-half strategy. First locate the middle node with slow and fast pointers, reverse the remaining list iteratively, then interleave nodes from the first half and the reversed second half until the list is reordered.
Is Reorder List asked at Google, Amazon, or Meta?
Reorder List is a common medium-level linked list problem frequently asked in technical interviews. Variants of this pattern have appeared in interviews at companies like Amazon, Meta, and Google because it tests pointer manipulation and multiple linked list techniques in one problem.