\[
\newcommand{\O}{\mathcal{O}}
\]
Reverse Linked List#
# # from leetcode
# class LinkedList:
# """Function to initialize the Linked List object."""
# head: Node = None
# def __init__(self):
# self.head = None
# def traverse(self) -> None:
# """Traverse through a linked list by printing all the nodes."""
# temp = self.head
# while temp is not None:
# print(temp.value)
# temp = temp.next
# def reverseList(self, head):
# """
# :type head: ListNode
# :rtype: ListNode
# """
# prev_node = None
# curr_node = head
# while curr_node:
# next_node = curr_node.next # Remember next node
# curr_node.next = prev_node # REVERSE! None, first time round.
# prev_node = curr_node # Used in the next iteration.
# curr_node = next_node # Move to next node.
# head = prev_node
# return head
from typing import *
class Node:
"""
The Node object is initialized with a value and can be linked to the next node by setting the next_node attribute to a Node object.
This node is Singular associated with Singly Linked List.
Attributes:
curr_node_value (Any): The value associated with the created node.
next_node (Node): The next node in the linked list. Note the distinction between curr_node_value and next_node, the former is the value of the node, the latter is the pointer to the next node.
Examples:
>>> node = Node(1)
>>> print(node.curr_node_value)
1
>>> print(node.next_node)
None
>>> node.next_node = Node(2)
>>> print(node.next_node.curr_node_value)
2
>>> print(node.next_node.next_node)
None
"""
curr_node_value: Any
next_node: Optional["Node"]
def __init__(self, curr_node_value: Any = None) -> None:
self.curr_node_value = curr_node_value
self.next_node = None
class LinkedList:
"""
The LinkedList object is initialized with a head node.
The `head` node (the first node) of a **Linked List** is of a `Node` object.
The `head` **entirely determines** the entirety of the whole **Linked List**.
Because knowing the head node of the **Linked List**, we will be able to know every single node that comes after it sequentially (if exists).
Attributes:
head (Node): The head node of the linked list.
"""
head: Node = None
def __init__(self) -> None:
self.head = None
@staticmethod
def traverse(head_node: Node) -> None:
"""Traverse the linked list and print the values of each node.
Args:
head_node (Node): The head node of a linked list.
Examples:
>>> first = Node(1)
>>> second = Node(2)
>>> third = Node(3)
>>> ll = LinkedList()
>>> ll.head = first
>>> ll.head.next_node = second
>>> ll.head.next_node.next_node = third
>>> ll.traverse(ll.head)
"""
temp_node = head_node
while temp_node is not None:
print(temp_node.curr_node_value)
temp_node = temp_node.next_node
if temp_node is None:
print("None")
@classmethod
def reverse(cls, head_node: Node) -> None:
"""Reverse the linked list.
Args:
head_node (Node): The head node of a linked list.
Examples:
>>> first = Node(1)
>>> second = Node(2)
>>> third = Node(3)
>>> ll = LinkedList()
>>> ll.head = first
>>> ll.head.next_node = second
>>> ll.head.next_node.next_node = third
>>> ll.traverse(ll.head)
>>> _ = ll.reverse(ll.head)
"""
# at this stage we must have a mental model
# 1 -> 2 -> 3 -> None is the original linked list
# 3 -> 2 -> 1 -> None is the reversed linked list
# we can do so by:
# 1. Start off with current node as the head node which is 1.
# 2. Set the next node of current node as None (note we set our prev_node as None). At this stage we are envisioning (1 -> None) and we should have prev_node as (1 -> None) now, it may not be obvious now but it will be clear later.
# 3. Now if we can have a node that holds the value of 2 (which is the next node of 1), we can set this node's next node as the prev_node (which is 1 -> None). Now we have (2 -> 1 -> None) and we should have prev_node as (2 -> 1 -> None) now.
# 4. By now, the rough algorithm is clear, as we go through the original linked list sequentially, we can get the current node and set its next node as the prev_node where prev_node is the nodes pointing backwards.
prev_node = None
curr_node = head_node
while curr_node is not None:
temp_node = curr_node
curr_node = curr_node.next_node
temp_node.next_node = prev_node
prev_node = temp_node
reversed_head_node = prev_node
print("Traverse reversed head node:")
cls.traverse(reversed_head_node)
return reversed_head_node
Note the pointer references can be confusing, permuting
curr_node = curr_node.next_node
temp_node.next_node = prev_node
will cause errors! Do you know why?
>>> first = Node(1)
>>> second = Node(2)
>>> third = Node(3)
>>> ll = LinkedList()
>>> ll.head = first
>>> ll.head.next_node = second
>>> ll.head.next_node.next_node = third
>>> ll.traverse(ll.head)
>>> _ = ll.reverse(ll.head)
1
2
3
None
Traverse reversed head node:
3
2
1
None
Time Complexity#
Time complexity: \(\O(n)\). We traverse the list containing \(n\) elements only once. Each lookup in the table costs only \(\O(1)\) time.
Loosely speaking, this means in each for loop from line 22 to 26, each line takes \(\O(1)\) time, so in a typical single iteration, we use around \(\O(3)\) time, and looping it \(n\) times takes
\[
n \cdot \O(3) \approx \O(3n) \approx \O(n)
\]
Space Complexity#
Space complexity: \(\O(n)\). The extra space required depends on the number of items stored in the dictionary seen, which stores at most \(n\) elements.