Reverse Linked List
Problem
https://leetcode.com/problems/reverse-linked-list/
Given the head of a singly linked list, reverse the list, and return
the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Constraints:
The number of nodes in the list is the range
[0, 5000].-5000 <= Node.val <= 5000
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
Pattern
Linked List, Recursion
Approaches
Explanation
Track the current node and prev node. At each step, store node.next
in a temporary variable. Set node.next to prev and then advance
prev and node.
Code
from __future__ import annotations
class ListNode:
"""Node in a linked list."""
def __init__(self, val: int, next: ListNode | None = None):
self.val = val
self.next = next
def to_list(self) -> list[int]:
list = []
while self is not None:
list.append(self.val)
self = self.next
return list
@classmethod
def from_list(cls, list: list[int]) -> ListNode | None:
head: ListNode | None = None
for el in list:
if head is None:
head = ListNode(el)
node = head
else:
node.next = ListNode(el)
node = node.next
return head
def reverseList(head: ListNode | None) -> ListNode | None:
prev = None
node = head
while node is not None:
original_next = node.next
node.next = prev
prev = node
node = original_next
return prev
Test
>>> from reverse_linked_list__iterative import ListNode, reverseList
>>> head = ListNode.from_list([1, 2, 3, 4, 5])
>>> reverseList(head).to_list()
[5, 4, 3, 2, 1]
>>> head = ListNode.from_list([1, 2])
>>> reverseList(head).to_list()
[2, 1]
>>> head = ListNode.from_list([1])
>>> reverseList(head).to_list()
[1]
Complexity
\(n\) is the number of nodes in the linked list
Measure |
Complexity |
Notes |
|---|---|---|
Time |
\(O(n)\) |
single pass through the list |
Auxiliary Space |
\(O(1)\) |