Algorithm Gymnastics 24 Middle of the Linked List

Middle of the LinkedList Write a method that returns an intermediate node in a LinkedList, specifying the beginning of a single linked list. If the total number of nodes in the LinkedList is even, it returns the second intermediate node.

Example

Input: 1 -> 2 -> 3 -> 4 -> 5 -> null Output: 3

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null Output: 4

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null Output: 4

Solution One of the brute force strategies is to first count the number of nodes in the LinkedList and then find the central node in the second iteration. It's important to be able to do this in a single iteration.

Use the fast and slow pointer methods to ensure that the fast pointer is always twice the node ahead of the slow pointer. Thus, when the fast pointer reaches the end of the LinkedList, the slow pointer points to the central node.

Implementation

class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next


def find_middle_of_linked_list(head):
  # Time Complexity O(N)
  # Space Complexity O(1)
  slow = head
  fast = head
  while (fast is not None and fast.next is not None):
    slow = slow.next
    fast = fast.next.next
  return slow


def main():
  head = Node(1)
  head.next = Node(2)
  head.next.next = Node(3)
  head.next.next.next = Node(4)
  head.next.next.next.next = Node(5)

  print("Middle Node: " + str(find_middle_of_linked_list(head).value))

  head.next.next.next.next.next = Node(6)
  print("Middle Node: " + str(find_middle_of_linked_list(head).value))

  head.next.next.next.next.next.next = Node(7)
  print("Middle Node: " + str(find_middle_of_linked_list(head).value))


main()

Recommended Posts

Algorithm Gymnastics 24 Middle of the Linked List
Algorithm Gymnastics 24 Reverse a Linked List
About the basics list of Python basics
Algorithm gymnastics 12
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
linked list
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Get the column list & data list of CASTable
Get the value of the middle layer of NN
[python] Check the elements of the list all, any
Algorithm Gymnastics 24 Subsets
Make a copy of the list in Python
I checked the list of shortcut keys of Jupyter
[Algorithm x Python] How to use the list
Search by the value of the instance in the list
Visualize the behavior of the sorting algorithm with matplotlib
[python] Get the list of classes defined in the module
Make a note of the list of basic Pandas usage
In the middle of development, we will introduce Alembic
Read the linked list in csv format with graph-tool
[Python] Get the list of ExifTags names of Pillow library
Implemented the algorithm of "Algorithm Picture Book" in Python3 (Heapsort)
[Python] Outputs all combinations of elements in the list
[Maya Python] Crush the contents of the script 2 ~ list Notes
I investigated the reinforcement learning algorithm of algorithmic trading
List of python modules
The beginning of cif2cell
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
The meaning of self
the zen of Python
List of activation functions (2020)
The story of sys.path.append ()
Algorithm Gymnastics 24 Cyclic Sort
Depth of nested list
Display of fractions (list)
Algorithm Gymnastics 19 No-repeat Substring
Revenge of the Types: Revenge of types
Try to get the function list of Python> os package
[Maya Python] Crush the contents of the script 3 ~ List unknown Plugins
Django + MongoDB development environment maintenance (in the middle of writing)
Scraping the Excel file of the list of stores handling regional coupons
Implemented the algorithm of "Algorithm Picture Book" in Python3 (Bubble Sort)
Get the number of specific elements in a python list
I implemented the FloodFill algorithm with TRON BATTLE of CodinGame.
Get the number of occurrences for each element in the list
Iterator that can scan forward from the middle of the sequence
Extract the value of dict or list as a string
Implemented the algorithm of "Algorithm Picture Book" in Python3 (selection sort)