Reorder List 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
Reorder List Solutions
✅Time: O(n)
✅Space: O(1)
C++
class Solution {
public:
void reorderList(ListNode* head) {
if (!head || !head->next)
return;
ListNode* mid = findMid(head);
ListNode* reversed = reverse(mid);
merge(head, reversed);
}
private:
ListNode* findMid(ListNode* head) {
ListNode* prev = nullptr;
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = nullptr;
return slow;
}
ListNode* reverse(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
void merge(ListNode* l1, ListNode* l2) {
while (l2) {
ListNode* next = l1->next;
l1->next = l2;
l1 = l2;
l2 = next;
}
}
};
Java
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null)
return;
ListNode mid = findMid(head);
ListNode reversed = reverse(mid);
merge(head, reversed);
}
private ListNode findMid(ListNode head) {
ListNode prev = null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
return slow;
}
private ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
private void merge(ListNode l1, ListNode l2) {
while (l2 != null) {
ListNode next = l1.next;
l1.next = l2;
l1 = l2;
l2 = next;
}
}
}
Python
class Solution:
def reorderList(self, head: ListNode) -> None:
def findMid(head: ListNode):
prev = None
slow = head
fast = head
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
prev.next = None
return slow
def reverse(head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
def merge(l1: ListNode, l2: ListNode) -> None:
while l2:
next = l1.next
l1.next = l2
l1 = l2
l2 = next
if not head or not head.next:
return
mid = findMid(head)
reversed = reverse(mid)
merge(head, reversed)
Watch Tutorial
Checkout more Solutions here