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
  3. 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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jonathan Chao

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