# 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

1. the number of nodes in the linked list
2. 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…

1. take the node from `i` pointer, set `next` to where `j` points
2. i ++
3. take the node from `j` pointer, set `next` to where `i` points
4. j — —
5. 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:

1. find the middle point of the list to divide the list into 2 parts
2. reverse the second part of the list

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, reversedhead1 = headwhile 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.

--

--

## More from Jonathan Chao

I am a software developer who has been in this industry for close to a decade. I share my experience to people who are or want to get into the industry

Love podcasts or audiobooks? Learn on the go with our new app.

## Jonathan Chao

219 Followers

I am a software developer who has been in this industry for close to a decade. I share my experience to people who are or want to get into the industry