206. Reverse Linked List
Recursion, Linked List ·Problem Statement
link: https://leetcode.com/problems/reverse-linked-list/ https://leetcode.cn/problems/reverse-linked-list/
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Input: head = [1,2]
Output: [2,1]
Input: head = []
Output: []
Solution Approach
To reverse a linked list, iteratively reassign the next pointers while traversing the list.
Algorithm
Initialization: Create a dummy node initialized to None, which will eventually be the new head of the reversed list. Reassign Pointers: For each node in the list, starting from head, update its next pointer to point to dummy, effectively reversing its direction. Traversal: Move the current node to the next node in the original list and repeat step 2 until the entire list is reversed.
Implement
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = None
while head:
tmp = head.next
head.next = dummy
dummy = head
head = tmp
return dummy