## Similar Problems

Similar Problems not available

# Reorder List - Leetcode Solution

## Companies:

LeetCode: Reorder List Leetcode Solution

Difficulty: Medium

Topics: stack linked-list two-pointers

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.

## Reorder List Solution Code

`1`