Real-world problems

Let’s look at a real-world problem that can be solved using the “In-place Reversal of a Linked List” pattern:

Assign Transactions

Stock transaction requests arrive and are inserted at the head of a singly linked list. The transactions need to be carried out by K brokers, such that each transaction is independent of all others. K is a positive integer and is less than or equal to the length of the linked list. There are a total of N transaction requests in the linked list. The first $⌊N/K⌋$ transactions need to be assigned to the first broker, the next $⌊N/K⌋$ transactions to the second broker, and so on. In the end, some transactions $(<N/K)$ may still be left in the original linked list. A first-come-first-serve policy will not be guaranteed globally, but the subset of transactions assigned to a specific broker will need to be carried out in the same order in which they arrived.

We do not want to split the original linked list. We will just pass a pointer to the transaction at the beginning of each K-node, set to different brokers. However, since this is a singly linked list and the order of the transactions in the linked list is opposite to the order in which they need to be processed, we will require each set of $⌊N/K⌋$ transactions in the linked list to be reversed. For this problem, we can assume that we are given a linked list of stock transaction requests, where an integer value represents each transaction request. We want to reverse the transactions in the list $⌊N/K⌋$ at a time and return the modified list. We may not alter the values, rather, we need to physically change the order of the transactions in the linked list.

Note: $⌊N/K⌋$ is guaranteed to be a positive integer that is less than or equal to the length of the linked list. If the number of transactions is not a multiple of $⌊N/K⌋$ then the transaction left in the end should remain as it is.

We may not use any additional space for our solution and we must solve the problem in $O(1)$ extra memory space.

The following examples may clarify this behavior:

Press + to interact

Python 3.5

from __future__ import print_function
class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next
  def print_list(self):
    temp = self
    while temp is not None:
      print(temp.value, end=" ")
      temp = temp.next
    print()
def reverse(head):
  previous, current, next = None, head, None
  while current is not None:
    next = current.next  # temporarily store the next node
    current.next = previous  # reverse the current node
    previous = current  # before we move to the next node, point previous to the current node
    current = next  # move on the next node
  return previous
def main():
  head = Node(2)
  head.next = Node(4)
  head.next.next = Node(6)
  head.next.next.next = Node(8)
  head.next.next.next.next = Node(10)
  print("Nodes of original LinkedList are: ", end='')
  head.print_list()
  result = reverse(head)
  print("Nodes of reversed LinkedList are: ", end='')
  result.print_list()
main()

Iteration No.	Line No.	current	next	previous	Reversed list	Remaining list
-	18	2	null	null	null	2 --> 4 --> 6 --> 8 --> 10 --> null
1	20	2	4	null	null	2 --> 4 --> 6 --> 8 --> 10 --> null
1	21	2	4	null	null <-- 2	4 --> 6 --> 8 --> 10 --> null
1	22	2	4	2	null <-- 2	4 --> 6 --> 8 --> 10 --> null
1	23	4	4	2	null <-- 2	4 --> 6 --> 8 --> 10 --> null
2	20	4	6	2	null <-- 2	4 --> 6 --> 8 --> 10 --> null
2	21	4	6	2	null <-- 2 <-- 4	6 --> 8 --> 10 --> null
2	22	4	6	4	null <-- 2 <-- 4	6 --> 8 --> 10 --> null
2	23	6	6	4	null <-- 2 <-- 4	6 --> 8 --> 10 --> null
3	20	6	8	4	null <-- 2 <-- 4	null <-- 2 <-- 4
3	21	6	8	4	null <-- 2 <-- 4 <-- 6	8 --> 10 --> null
3	22	6	8	6	null <-- 2 <-- 4 <-- 6	8 --> 10 --> null
3	23	8	8	6	null <-- 2 <-- 4 <-- 6	8 --> 10 --> null
4	20	8	10	6	null <-- 2 <-- 4 <-- 6	8 --> 10 --> null
4	21	8	10	6	null <-- 2 <-- 4 <-- 6 <--8	10 --> null
4	22	8	10	8	null <-- 2 <-- 4 <-- 6 <--8	10 --> null
4	23	10	10	8	null <-- 2 <-- 4 <-- 6 <--8	10 --> null
5	20	10	null	8	null <-- 2 <-- 4 <-- 6 <--8	10 --> null
5	21	10	null	8	null <-- 2 <-- 4 <-- 6 <--8 <--10	null
5	22	10	null	10	null <-- 2 <-- 4 <-- 6 <--8 <--10	null
5	23	null	null	10	null <-- 2 <-- 4 <-- 6 <--8 <--10	null

Trace generation

A few functions have been added to the code below to produce the execution trace. Details are as follows:

The function print_list_with_forwardarrow has been added to print out the linked list nodes with arrows pointing forward. It is used to print the remaining LinkedList nodes in each iteration of the reverse function.
The function print_list_with_backarrow has been added to print out the linked list nodes with the arrows pointing backward. It is used to print the reversed LinkedList nodes in each iteration of the reverse function.

Press + to interact

Python 3.5

from __future__ import print_function
class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next
  def print_list(self):
    temp = self
    while temp is not None:
      print(temp.value, end=" ")
      temp = temp.next
    print()
  def print_list_with_backarrow(self):
    temp = self
    nodes = []
    # add values of nodes from the linkedlist to the array "nodes"
    while temp is not None:
      nodes.append(temp.value)
      temp = temp.next
    # print the array "nodes" in the reverse order seperated by "<--"
    for (index,value) in enumerate(reversed(nodes)) :
      if index == 0:
         print("null <--",end=" ")
      else:
         print ("<--",end=" ")
      print(value, end=" ")
  def print_list_with_forwardarrow(self):
    temp = self
    while temp is not None:
      print(temp.value, end=" ") #print node value
      
      temp = temp.next
      if temp is None:
        print("--> null") # if this is the last node, print null at the end
      else:
        print("-->", end=" ") 
    print()
def reverse(head):
  previous, current, next = None, head, None
  index = 0
  while current is not None:
    print("Iteration " + str(index) + ": ",end=" ")
    index +=1
    next = current.next  # temporarily store the next node
    current.next = previous  # reverse the current node
    previous = current  # before we move to the next node, point previous to the current node
    
    current.print_list_with_backarrow()
    
    current = next  # move on the next node
    if current is not None:
      print("   ||   ", end=" ")
      current.print_list_with_forwardarrow()
  return previous
def main():
  head = Node(2)
  head.next = Node(4)
  head.next.next = Node(6)
  head.next.next.next = Node(8)
  head.next.next.next.next = Node(10)
  print("The original linked list: ", end=" ")
  head.print_list_with_forwardarrow()
  result = reverse(head)
  print("\n\nThe reversed linked list:   ", end='')
  result.print_list_with_backarrow()
main()

Iteration No.	Line No.	current	next	previous	Reversed list	Remaining list
-	18	5	null	null	null	5 --> 9 --> 11 --> null
1	20	5	9	null	null	5 --> 9 --> 11 --> null
1	21	5	9	null	null <-- 5	9 --> 11 --> null
1	22	5	9	5	null <-- 5	9 --> 11 --> null
1	23	9	9	5	null <-- 5	9 --> 11 --> null
...	...	...	...	...	...	...
...	...	...	...	...	...	...

Pattern: Sliding Window

Pattern: Two Pointers

Pattern: Fast & Slow pointers

Pattern: In-place Reversal of a LinkedList

Pattern: Tree Breadth First Search

Pattern: Tree Depth First Search

Pattern: Modified Binary Search

Pattern: Top 'K' Elements

Pattern: K-way merge

Pattern: Subsets

Pattern : 0/1 Knapsack (Dynamic Programming)

Pattern: Topological Sort

Pattern: Two Heaps

Pattern: Cyclic Sort

Pattern: Bitwise XOR

Pattern: Merge Intervals

Introduction

Real-world problems

Assign Transactions

Dry-run templates

Sample input #1

Sample input #2

Trace generation