Algorithm Gymnastics 24 Reverse a Linked List

Reverse a LinkedList Specifying the beginning of a single LinkedList reverses the LinkedList. Write a function that returns a new head for the inverted LinkedList.

Example

Screen Shot 2020-08-07 at 21.27.40.png

Solution You can use the three pointers previous, current, and next to reverse the LinkedList in a single iteration.

Implementation

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()

Recommended Posts

Algorithm Gymnastics 24 Reverse a Linked List
Algorithm Gymnastics 24 Middle of the Linked List
Algorithm gymnastics 12
Algorithm gymnastics 10
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
Algorithm Gymnastics 22 Squaring a Sorted Array
List reverse operation
A * algorithm (Python edition)
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
Understand Linked List Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Let Code Day78 Starting from Zero "206. Reverse Linked List"
A comment on Boruta algorithm
Python list is not a list