# 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; } } }