Reorder List
Reorder List Problem – Medium Level Problem
You are given the head of a singly linked list for Reorder List Problem:
- For a linked list of length 7, the initial node positions are: 0,1,2,3,4,5,6
- Reorder the nodes to follow this pattern: 0,6,1,5,2,4,3
- In general, for a list of length n, the nodes are rearranged as: 0,n−1,1,n−2,2,n−3,…
Note:
You cannot change the values in the nodes; instead, you must adjust the order of the nodes themselves.
Example 1:
Input: head = [2,4,6,8]
Output: [2,8,4,6]
Output: [2,8,4,6]
Example 2:
Input: head = [2,4,6,8,10]
Output: [2,10,4,8,6]
Output: [2,10,4,8,6]
Constraints:
- 1 <= Length of the list <= 1000.
- 1 <= Node.val <= 1000
Hints to Solve Reorder List
Recommendation for Time and Space Complexity (For Reorder List)
You should aim for a solution with O(n) time and O(1) space, where n is the length of the given list.
Hint 1 :
- A brute force solution would be to store the node values of the list in an array, reorder the values, and create a new list.
- Can you think of a better way?
- Perhaps you can try reordering the nodes directly in place, avoiding the use of extra space.
Hint 2 :
- For example, consider the list [1, 2, 3, 4, 5]. To reorder the list, we connect the first and last nodes, then continue with the second and second-to-last nodes, and so on.
- Essentially, the list is split into two halves: the first half remains as is, and the second half is reversed and merged with the first half.
- For instance, [1, 2] will merge with the reversed [5, 4, 3].
- Can you figure out a way to implement this reordering process? Maybe dividing the list into two halves could help.
Hint 3 :
- We can divide the list into two halves using the fast and slow pointer approach, which helps identify the midpoint of the list. This allows us to split the list into two halves, with the heads labeled as l1 and l2.
- Next, we reverse the second half (l2). After these steps, we proceed to reorder the two lists by iterating through them node by node, updating the next pointers accordingly.
There are mainly 3 approach to solve Reorder List problem:
- Brute Force Method
- Recursion Method
- Reverse And Merge Method
1. Brute Force Method
In this approach, we store all the nodes of the linked list in an array to access them by index. Then, we reorder the nodes by modifying their pointers according to the required pattern. This method is simple but uses extra space for the array.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if (!head) return;
vector nodes;
ListNode* cur = head;
while (cur) {
nodes.push_back(cur);
cur = cur->next;
}
int i = 0, j = nodes.size() - 1;
while (i < j) {
nodes[i]->next = nodes[j];
i++;
if (i >= j) break;
nodes[j]->next = nodes[i];
j--;
}
nodes[i]->next = nullptr;
}
};
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if (head == null) {
return;
}
List nodes = new ArrayList<>();
ListNode cur = head;
while (cur != null) {
nodes.add(cur);
cur = cur.next;
}
int i = 0, j = nodes.size() - 1;
while (i < j) {
nodes.get(i).next = nodes.get(j);
i++;
if (i >= j) {
break;
}
nodes.get(j).next = nodes.get(i);
j--;
}
nodes.get(i).next = null;
}
}
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
if not head:
return
nodes = []
cur = head
while cur:
nodes.append(cur)
cur = cur.next
i, j = 0, len(nodes) - 1
while i < j:
nodes[i].next = nodes[j]
i += 1
if i >= j:
break
nodes[j].next = nodes[i]
j -= 1
nodes[i].next = None
JavaScript
/**
* Definition for singly-linked list.
* class ListNode {
* constructor(val = 0, next = null) {
* this.val = val;
* this.next = next;
* }
* }
*/
class Solution {
/**
* @param {ListNode} head
* @return {void}
*/
reorderList(head) {
if (!head) return;
const nodes = [];
let cur = head;
while (cur) {
nodes.push(cur);
cur = cur.next;
}
let i = 0, j = nodes.length - 1;
while (i < j) {
nodes[i].next = nodes[j];
i++;
if (i >= j) break;
nodes[j].next = nodes[i];
j--;
}
nodes[i].next = null;
}
}
2. Recursion Method
Using recursion, we traverse to the end of the list and backtrack to reorder the nodes. By maintaining pointers during backtracking, we adjust the node connections to achieve the desired order. This method avoids additional data structures but requires extra stack space.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
head = rec(head, head->next);
}
private:
ListNode* rec(ListNode* root, ListNode* cur) {
if (cur == nullptr) {
return root;
}
root = rec(root, cur->next);
if (root == nullptr) {
return nullptr;
}
ListNode* tmp = nullptr;
if (root == cur || root->next == cur) {
cur->next = nullptr;
} else {
tmp = root->next;
root->next = cur;
cur->next = tmp;
}
return tmp;
}
};
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
head = rec(head, head.next);
}
private ListNode rec(ListNode root, ListNode cur) {
if (cur == null) {
return root;
}
root = rec(root, cur.next);
if (root == null) {
return null;
}
ListNode tmp = null;
if (root == cur || root.next == cur) {
cur.next = null;
} else {
tmp = root.next;
root.next = cur;
cur.next = tmp;
}
return tmp;
}
}
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
def rec(root: ListNode, cur: ListNode) -> ListNode:
if not cur:
return root
root = rec(root, cur.next)
if not root:
return None
tmp = None
if root == cur or root.next == cur:
cur.next = None
else:
tmp = root.next
root.next = cur
cur.next = tmp
return tmp
head = rec(head, head.next)
JavaScript
/**
* Definition for singly-linked list.
* class ListNode {
* constructor(val = 0, next = null) {
* this.val = val;
* this.next = next;
* }
* }
*/
class Solution {
/**
* @param {ListNode} head
* @return {void}
*/
reorderList(head) {
head = this.rec(head, head.next);
}
/**
* @param {ListNode} root
* @param {ListNode} cur
* @return {ListNode}
*/
rec(root, cur) {
if (cur === null) {
return root;
}
root = this.rec(root, cur.next);
if (root === null) {
return null;
}
let tmp = null;
if (root === cur || root.next === cur) {
cur.next = null;
} else {
tmp = root.next;
root.next = cur;
cur.next = tmp;
}
return tmp;
}
}
3. Reverse and Merge Method
Efficient approach splits the list into two halves, reverses the second half, and merges it with the first half in alternating order. It uses the fast and slow pointer technique to divide the list, ensuring O(1) space complexity while achieving the desired reordering.
- Time complexity: O(n)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head->next;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* second = slow->next;
ListNode* prev = slow->next = nullptr;
while (second != nullptr) {
ListNode* tmp = second->next;
second->next = prev;
prev = second;
second = tmp;
}
ListNode* first = head;
second = prev;
while (second != nullptr) {
ListNode* tmp1 = first->next;
ListNode* tmp2 = second->next;
first->next = second;
second->next = tmp1;
first = tmp1;
second = tmp2;
}
}
};
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode second = slow.next;
ListNode prev = slow.next = null;
while (second != null) {
ListNode tmp = second.next;
second.next = prev;
prev = second;
second = tmp;
}
ListNode first = head;
second = prev;
while (second != null) {
ListNode tmp1 = first.next;
ListNode tmp2 = second.next;
first.next = second;
second.next = tmp1;
first = tmp1;
second = tmp2;
}
}
}
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
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:
tmp = second.next
second.next = prev
prev = second
second = tmp
first, second = head, prev
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2JavaScript
/**
* Definition for singly-linked list.
* class ListNode {
* constructor(val = 0, next = null) {
* this.val = val;
* this.next = next;
* }
* }
*/
class Solution {
/**
* @param {ListNode} head
* @return {void}
*/
reorderList(head) {
let slow = head;
let fast = head.next;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
let second = slow.next;
let prev = (slow.next = null);
while (second !== null) {
const tmp = second.next;
second.next = prev;
prev = second;
second = tmp;
}
let first = head;
second = prev;
while (second !== null) {
const tmp1 = first.next;
const tmp2 = second.next;
first.next = second;
second.next = tmp1;
first = tmp1;
second = tmp2;
}
}
}
