# LeetCode 143. Reorder List

## Description

https://leetcode.com/problems/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`

## Explanation

Find the first half and second half of the node list. Keep the first half order, and reverse the second half node list. Then mix the nodes from the first half list and the second half list.

## Python Solution

``````# 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:
"""
"""
count = 0

while current != None:
current = current.next
count += 1

if count % 2 == 0:
mid = count // 2
else:
mid = (count + 1) // 2

first_half = []
second_half = []

index = 0

while current != None:
if index < mid:
first_half.append(current)
else:
second_half.append(current)

current = current.next
index += 1

second_half = list(reversed(second_half))

current = first_half.pop(0)

for i in range(count - 1):
if i % 2 == 0:
current.next = second_half.pop(0)
else:
current.next = first_half.pop(0)

current = current.next

current.next = None

``````
• Time Complexity: O(N).
• Space Complexity: O(N).