# The Blind 75 Leetcode Series: Reorder List

Today, we are working on 143. 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.

We have a linked list, and we want to reorder the linked nodes (i.e. change the `next`

to point to a new node). The problem itself is simple enough, but we can check for

- the number of nodes in the linked list
- node values and if they are unique

If the interviewers tell us that there a big but finite number of nodes and the node values are not necessarily unique, then we can proceed.

The way it should be rearranged is “one from the front, one from the back”, then repeat. So it’s natural to think of a two-pointer approach, where one pointer points to the beginning of the list, moving forward, and another pointer at the end of the list, moving backward.

The next is to find a way to get to the end of the list. One approach is to use a new list as tracker. We traverse through the list, record each node in the new list, then we can easily manipulate with the pointers moving up and down the list.

`node_list = []`

while head:

node_list.append(head)

head = head.next

now the `node_list`

has all nodes inside. We have have `i, j = 0, len(node_list) — 1`

to get to the right position. Then we can…

- take the node from
`i`

pointer, set`next`

to where`j`

points - i ++
- take the node from
`j`

pointer, set`next`

to where`i`

points - j — —
- repeat until i > j

We need to make sure the conditional should cover the node where i and j meet (if they meet), and we need to make that node’s `next`

point to nothing to complete the process. The overall code looks like this

`def reorderList(head):`

node_list = []

last_node = head

while last_node:

node_list.append(last_node)

last_node = last_node.next

i, j = 1, len(node_list) - 1

while i <= j:

head.next = node_list[j]

j -= 1

head = head.next

head.next = node_list[i]

head = head.next

i += 1

if i == j:

head.next = node_list[i]

head = head.next

head.next = None

The problem asks us not to return anything. The program will be able to read from `head`

directly, so we don’t need a `return`

.

What’s the time complexity for this approach? We simply traverse through the linked list and visit every node twice, which makes it **O(n)** where n in the length of the linked list.

This approach does the trick, but much like the last problem we did, we run into problem where the linked list might be too long that we have to track too many nodes in our tracker. Can we do it without the tracker?

Not quite, but we can shorten the length of space we need.

This approach uses the fact that we can actually divide this original list into 2 parts at the middle. Instead of tracking the second part of the list backwards, we simply reverse that part of linked list. Now we have 2 linked lists, and we just take turn fetching nodes. Therefore, we need to do 3 things:

- find the middle point of the list to divide the list into 2 parts
- reverse the second part of the list
- merge the 2 linked lists to form final answer

First, the finding middle part. This can be done with the hare and tortoise approach introduced in this problem. We have 2 pointers, which 1 pointer moving twice the speed as the other. When the faster pointer reaches the end, the slower one should be right at the middle.

`def find_middle(head):`

slow, fast = head, head

while fast and fast.next:

slow = slow.next

fast = fast.next.next

return slow

Second, we reverse the part of list that’s on the right of the `middle`

. This is simply a reverse-a-linked-list operation.

`def reverse_list(head):`

previous, current = None, head

while current:

next_node = current.next

current.next = previous

previous = current

current = next_node

return previous

Now we have 2 lists. We just need to put them together accoridngly

`head2 = reverse_list(find_middle(head)) `*# this gets the second half of the list, reversed*

head1 = head

while head2.next:

head1.next, head1 = head2, head1.next *# point to h2, then move h1*

head2.next, head2 = head1, head2.next *# point to h1, then move h2*

So putting everything together, it becomes

def reorderList(head):

def find_middle(head):

slow, fast = head, head

while fast and fast.next:

slow = slow.next

fast = fast.next.next

return slow def reverse_list(head):

previous, current = None, head

while current:

next_node = current.next

current.next = previous

previous = current

current = next_node

return previous head2 = reverse_list(find_middle(head))

head1 = head

while head2.next:

head1.next, head1 = head2, head1.next

head2.next, head2 = head1, head2.next

What’s the time complexity? We are still traversing through the linked list, visiting every node, so it’s still **O(n)**

Whether you choose the first or second approach, the problem tests for the ability to track where the pointers are and how to move them correctly. It’s actually best to draw the nodes on paper and walk it through once. Then the relationship becomes very clear.

That’s it! Another problem down.

*Buy my a coffee: **https://www.buymeacoffee.com/jonathanckz*