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:
- Splitting the list into two halves
- Reversing the second half of the list
- Combining the two halves of the list
Let’s go through each of these parts in detail:
- 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.
- 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.
- 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:
if not head:
return
# step 1: split the list into two halves
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
left, right = head, slow.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
return head
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
/**
* 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) {
// if head is null or there is only one node in the list, return
if (head == null || head.next == null) {
return;
}
// find the middle of the list
ListNode slow = head;
ListNode fast = head;
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 first = head;
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:
"""
Do not return anything, modify head in-place instead.
"""
if not head:
return
# find the middle of the list
slow = fast = head
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
first = head
second = middle.next
while second and first:
middle.next = second
temp = second.next
second.next = first
first = first.next
second = temp
middle.next = first/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {void} Do not return anything, modify head in-place instead.
*/
var reorderList = function(head) {
if (!head || !head.next) return head;
let slow = head;
let fast = head;
// 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 first = head;
let second = prev;
while (second.next) {
let next1 = first.next;
let next2 = second.next;
first.next = second;
second.next = next1;
first = next1;
second = next2;
}
};/**
* 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) {
// Base case
if (!head || !head->next) return;
// Find the middle of the list
ListNode* slow = head;
ListNode* fast = head;
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
ListNode* first_half = head;
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* reverseList(ListNode* head) {
ListNode* prev = nullptr;
while (head) {
ListNode* tmp = head->next;
head->next = prev;
prev = head;
head = tmp;
}
return prev;
}
};/**
* Definition for singly-linked list.
* 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 {
public void ReorderList(ListNode head) {
//Check for empty or single node list
if(head == null || head.next == null)
{
return;
}
//Find the middle of the list
ListNode slow = head;
ListNode fast = head;
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 first = head;
ListNode second = prev;
while(first != slow)
{
ListNode temp = first.next;
first.next = second;
first = temp;
temp = second.next;
second.next = first;
second = temp;
}
}
}