# Solution For Reorder List

Problem Statement:

Given the head of a singly linked list, reorder it to a new list where each node in the new list is alternatively from the beginning and end of the original list.

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]

Solution:

To solve this problem, we can divide it into three main parts:

1. Splitting the list into two halves
2. Reversing the second half of the list
3. Combining the two halves of the list

Let’s go through each of these parts in detail:

1. Splitting the list into two halves

We can use the fast-and-slow pointer technique to split the linked list into two halves. Essentially, we start two pointers, one that moves one step at a time (slow pointer) and the other that moves two steps at a time (fast pointer). Eventually, when the fast pointer reaches the end of the list, the slow pointer will be at the midpoint of the list.

1. Reversing the second half of the list

After we have split the list into two halves (say, left and right), we need to reverse the second half (right half). To do this, we can again use the fast-and-slow pointer technique, but this time we start from the midpoint of the list (where the slow pointer is). We use the fast pointer to keep track of the previous node, and the slow pointer to keep track of the current node. At each step, we make the current node point to the previous node, and move both pointers one step forward. We continue until the slow pointer reaches the end of the list.

1. Combining the two halves of the list

Once we have both halves of the list, we can combine them by alternately picking one node from each half until we reach the end of both halves. If one half is longer than the other, we simply append the remaining nodes to the end of the new list.

Here’s the Python implementation of the above approach:

class Solution:
def reorderList(self, head: ListNode) -> None:
return

``````    # step 1: split the list into two halves
while fast and fast.next:
slow = slow.next
fast = fast.next.next
slow.next = None

# step 2: reverse the second half of the list
prev, curr = None, right
while curr:
nxt = curr.next
curr.next = prev
prev, curr = curr, nxt
right = prev

# step 3: combine the two halves of the list
while right:
nxt1, nxt2 = left.next, right.next
left.next = right
right.next = nxt1
left, right = nxt1, nxt2

``````

Time Complexity: O(n), where n is the number of nodes in the linked list.
Space Complexity: O(1), since we are reusing the existing nodes in the linked list.

## Step by Step Implementation For Reorder 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 {
// if head is null or there is only one node in the list, return
return;
}

// find the middle of the list
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}

// reverse the second half of the list
ListNode prev = null;
ListNode curr = slow;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}

// merge the two halves of the list
ListNode second = prev;
while (second.next != null) {
ListNode temp1 = first.next;
ListNode temp2 = second.next;
first.next = second;
second.next = temp1;
first = temp1;
second = temp2;
}
}
}```
```# 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: ListNode) -> None:
"""
"""
return

# find the middle of the list
while fast and fast.next:
slow = slow.next
fast = fast.next.next

# reverse the second half of the list
middle = slow
prev = None
curr = slow.next

while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
middle.next = prev

# merge the two halves
second = middle.next

while second and first:
middle.next = second
temp = second.next
second.next = first
first = first.next
second = temp
middle.next = first```
```/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
*/

// Find the middle of the list
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}

// Reverse the second half of the list
let prev = null;
let curr = slow;
while (curr) {
let next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}

// Merge the two halves of the list
let second = prev;
while (second.next) {
let next1 = first.next;
let next2 = second.next;
first.next = second;
second.next = next1;
first = next1;
second = next2;
}
};```
```/**
* 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:

// Base case

// Find the middle of the list
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}

// Reverse the second half of the list
ListNode* second_half = reverseList(slow->next);
slow->next = nullptr;

// Merge the two halves
while (second_half) {
ListNode* tmp = second_half->next;
second_half->next = first_half->next;
first_half->next = second_half;
first_half = first_half->next->next;
second_half = tmp;
}
}

ListNode* prev = nullptr;
}
return prev;
}
};```
```/**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int val=0, ListNode next=null) {
*         this.val = val;
*         this.next = next;
*     }
* }
*/
public class Solution {
//Check for empty or single node list
{
return;
}

//Find the middle of the list
while(fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
}

//Reverse the second half of the list
ListNode prev = null;
ListNode curr = slow;
while(curr != null)
{
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}

//Merge the two halves of the list
ListNode second = prev;
while(first != slow)
{
ListNode temp = first.next;
first.next = second;
first = temp;

temp = second.next;
second.next = first;
second = temp;
}
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]