- Published on
Reverse Linked List
- Authors
- Name
- Alex Noh
Introduction
Given the head of a singly linked list, reverse the list, and return the reversed list. The interface is described below.
list_node.py
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next: Optional['ListNode']=None):
self.val = val
self.next = next
# This will form a linked list where the order is 1 -> 2 -> 2 -> 1
fourth = ListNode(val=1)
third = ListNode(val=2, next=fourth)
second = ListNode(val=2, next=third)
first = ListNode(val=1, next=second)
Solutions
1. Using recursion
To reverse a linked list using recursion, we create a function named reverse. This function takes two parameters: node, the current node being processed, and prev, which points to the previous node. We start the recursion from the head of the list and call the reverse() function recursively.
Here's the implementation:
recursion.py
from typing import Optional
def reverse_linked_list(head: ListNode) -> ListNode:
def reverse(node: ListNode, prev: Optional[ListNode] = None):
if not node:
return prev
next_node = node.next
node.next = prev
return reverse(next_node, node)
return reverse(head)
2. Using Iteration
To reverse a linked list using iteration, we create a function that iteratively processes each node, reversing the links as we go.
Here's the implementation:
iteration.py
from typing import Optional
def reverse_linked_list(head: ListNode) -> ListNode:
node, prev = head, None
while node:
next_node, node.next = node.next, prev
prev, node = node, next_node
return prev