DSA Visualizations | Hello Interview

Reorder List

DESCRIPTION (credit Leetcode.com)

Given a reference head of type ListNode that is the head of a singly linked list, reorder the list in-place such that the nodes are reordered to form the following pattern:

1st node -> last node -> 2nd node -> 2nd to last node -> 3rd node ...

EXAMPLES

Example 1: input:

output:

Example 2: input:

output:

Solution

The first observation is that we can create our final list by merging two smaller lists: the first half of the original list and the reversed second half of the original list.

For example, if our original list is 5 -> 4 -> 3 -> -> 2 -> 1, then the first half is 5 -> 4 -> 3 and the reversed second half is 1 -> 2. We can merge these two lists to get the final list 5 -> 1 -> 4 -> 2 -> 3.

Above: The first half of the original list

Below: The reversed second half of the original list

With that established, we can focus on getting the reverse of the 2nd half of the list. This breaks down to first finding the middle node of the list, and then reversing the direction of the nodes starting from the middle node to the end of the list.

Put together, the solution involves three steps, each of which involve 3 fairly common linked list operations:

Finding the middle of the linked list (using fast and slow pointers).
Reversing the nodes between the middle and the end of the linked list.
Merging the first half of the linked list with the reversed second half.

Step 1: Find the Middle of the Linked List

This step can be done using fast and slow pointers, which involves initializing two pointers, fast and slow, at the head of the linked list, and then iterating until fast reaches the end of the list. At each iteration, slow moves one node forward and fast moves two nodes forward. When fast reaches the tail node of the list, slow will point to the middle node in the list.


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

initialize pointers

0 / 2

When there are an even number of nodes, fast will equal to None after moving past the tail node, and slow will be the first node of the second half of the list. In the case below, there are 4 nodes, so slow will point to the 3rd node.


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

initialize pointers

0 / 2

Step 2: Reverse second half of list

At this point, slow points to the middle node in the list. Next, we want to reverse the direction of the pointers of each node starting from slow to the tail of the list.

Reversing the nodes in a linked list is a common problem that can be solved by iterating over each node that needs to be reversed. The key idea is to maintain three pointers, prev, curr, and next_, where prev points to the previous node, curr points to the node with the pointer we want to reverse, and next_ points to the next node in the iteration.

At each iteration, we:

save the next node in the iteration by setting next_ = curr.next
reverse the pointer by setting curr.next = prev
move pointers for the next iteration by set curr = next_ and prev = curr


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

fast = fast.next.next, slow = slow.next

0 / 10

You need the next_pointer to store the next node in the iteration before overwriting curr.next = prev. If you don't store the next node in the iteration, you will lose the reference to the rest of the linked list.

Step 3: Merge first half with reversed second half

At this point, when curr is None, then prev will be the head of the reversed second half of the list. We can then merge the first half of the list with the reversed second half by iterating over the two halves and updating the pointers of the nodes.

We can do so by initializing two pointers: first, which points to the head of the first half of the list, and second, which points to the head of the reversed second half of the list, which is initially prev.


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

curr = next_, prev = curr

0 / 1

From there, we want to merge the nodes at first and second together, with first coming before second. To do so, we first set first.next = second. And since we are over-writing first.next, we need to simultaneously advance first = first.next so that we have access to the next node in the first half of the list.


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

first = head, second = prev

0 / 1

Now the first node in the original list and the first node in the reversed second half are connected, so we need to connect the 2nd node in the original list with the first node in the reversed second half. We can do so by setting second.next = first and making sure we simultaneously advance second = second.next so that we have access to the next node in the reversed second half.


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

first.next = 1, first = 4

0 / 1

At this point, the first three nodes in our original linked list are correctly ordered, and first and second are pointing to the next nodes in each half that we need to merge together. So we can continue the merge until second has reached the end of the reversed second half of the list, at which point we can return None.


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

second.next = 4, second = 2

0 / 3

Code

To construct the linked list that is used in the animation below, provide a list of integers nodes. Each integer in nodes is used as the value of a node in the linked list, and the order of the integers in the list will be the order of the nodes in the linked list.

For example, if nodes = [1, 2, 3], the linked list will be 1 -> 2 -> 3.


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

reorder list

0 / 19

Edge Cases

Empty List

When the linked list is empty, the initial check for head being None will return None immediately.


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

reorder list

0 / 1

head = []

Single Node

When the linked list has one node, the initial check for head.next being None will return head immediately.


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

reorder list

0 / 1

head = [1]

Two Nodes

When the linked list has two nodes, the linked list is already in the correct order.

The while loop to find the middle node iterates once, with slow pointing to the 2nd node.
The while loop to reversing the second half runs once, but since there is only one node in the 2nd half of the list, no pointers are updated, and prev points to the 2nd node.
The while loop to merge the two halves doesn't run, as second.next is None.


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

reorder list

0 / 8

head = [1, 2]

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the linked list. We iterate over the linked list three times: once to find the middle node, once to reverse the second half of the list, and once to merge the two halves together. Each iteration takes O(n) time.

Space Complexity: O(1). We only use a constant amount of extra space to store pointers and temporary variables. In other words, regardless if the linked list has 10 nodes or 10,000 nodes, we will still use two pointers to find the middle node, three pointers to reverse the second half of the list, and two pointers to merge the two halves together.

Next: Swap Nodes in Pairs

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Remove Nth Node From End of List

Swap Nodes in Pairs

Reorder List

DESCRIPTION (credit Leetcode.com)

Given a reference head of type ListNode that is the head of a singly linked list, reorder the list in-place such that the nodes are reordered to form the following pattern:

1st node -> last node -> 2nd node -> 2nd to last node -> 3rd node ...

EXAMPLES

Example 1: input:

output:

Example 2: input:

output:

Solution

The first observation is that we can create our final list by merging two smaller lists: the first half of the original list and the reversed second half of the original list.

Above: The first half of the original list

Below: The reversed second half of the original list

Put together, the solution involves three steps, each of which involve 3 fairly common linked list operations:

Finding the middle of the linked list (using fast and slow pointers).
Reversing the nodes between the middle and the end of the linked list.
Merging the first half of the linked list with the reversed second half.

Step 1: Find the Middle of the Linked List


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

initialize pointers

0 / 2


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

initialize pointers

0 / 2

Step 2: Reverse second half of list

At this point, slow points to the middle node in the list. Next, we want to reverse the direction of the pointers of each node starting from slow to the tail of the list.

At each iteration, we:

save the next node in the iteration by setting next_ = curr.next
reverse the pointer by setting curr.next = prev
move pointers for the next iteration by set curr = next_ and prev = curr


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

fast = fast.next.next, slow = slow.next

0 / 10

Step 3: Merge first half with reversed second half


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

curr = next_, prev = curr

0 / 1


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

first = head, second = prev

0 / 1


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

first.next = 1, first = 4

0 / 1


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

second.next = 4, second = 2

0 / 3

Code

For example, if nodes = [1, 2, 3], the linked list will be 1 -> 2 -> 3.


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

reorder list

0 / 19

Edge Cases

Empty List

When the linked list is empty, the initial check for head being None will return None immediately.


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

reorder list

0 / 1

head = []

Single Node

When the linked list has one node, the initial check for head.next being None will return head immediately.


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

reorder list

0 / 1

head = [1]

Two Nodes

When the linked list has two nodes, the linked list is already in the correct order.

The while loop to find the middle node iterates once, with slow pointing to the 2nd node.
The while loop to reversing the second half runs once, but since there is only one node in the 2nd half of the list, no pointers are updated, and prev points to the 2nd node.
The while loop to merge the two halves doesn't run, as second.next is None.


def reorderList(head):
  if not head or not head.next:
    return head

  # find middle node
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of list
  prev, curr = None, slow
  while curr:
    next_ = curr.next
    curr.next = prev
    prev, curr = curr, next_

  # merge first and reversed second half of list
  first, second = head, prev
  while second.next:
    first.next, first = second, first.next
    second.next, second = first, second.next

  return head

reorder list

0 / 8

head = [1, 2]

Complexity Analysis

Next: Swap Nodes in Pairs

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA Guided Practice Hello Interview Premium

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103