206. Reverse Linked List
## description
## 206. Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
1Input: head = [1,2,3,4,5]
2Output: [5,4,3,2,1]Example 2:
1Input: head = [1,2]
2Output: [2,1]Example 3:
1Input: head = []
2Output: []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?
## notes
### Intuition
To reverse a linked list, we need to flip each node's pointer to point backward instead of forward. This can be done iteratively by maintaining references to the previous and current nodes.
### Implementation
Use two pointers: curr starting at head and prev starting at None. For each node, save curr.next in a temp variable (we'll lose access to it otherwise), then reverse the link by setting curr.next = prev. Advance by setting prev = curr and curr = temp. When done, prev points to the new head.
### Edge-cases
The order of operations is critical. Always save the next pointer before overwriting it. An empty list or single-node list works naturally—prev will be None or the single node respectively.
- –Time: O(n) — visit each node once
- –Space: O(1) — only using pointers
### Complexity
## solution
1from typing import Optional
2from lcutils import ListNode
3
4# Definition for singly-linked list.
5# class ListNode:
6# def __init__(self, val=0, next=None):
7# self.val = val
8# self.next = next
9
10class Solution:
11 def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
12 curr = head
13 prev = None
14 while curr:
15 temp = curr.next
16 curr.next = prev
17 prev = curr
18 curr = temp
19 return prev
20
21
22
23
24if __name__ == "__main__":
25 # Include one-off tests here or debugging logic that can be run by running this file
26 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
27 solution = Solution()
28