Reverse Linked List
EasyAcceptance: 72.5%
Problem Statement
Given the head of a singly linked list, reverse the list, and return the reversed list.
Constraints:
- The number of nodes in the list is the range [0, 5000]
- -5000 <= Node.val <= 5000
Input Format:
- The head of a linked list
Output Format:
- The head of the reversed linked list
Examples:
Example 1:
Input:
head = [1,2,3,4,5]
Output:
[5,4,3,2,1]
Explanation:
The linked list 1->2->3->4->5 is reversed to 5->4->3->2->1
Example 2:
Input:
head = [1,2]
Output:
[2,1]
Explanation:
The linked list 1->2 is reversed to 2->1
Solutions
Iterative Approach
Time: O(n)
Space: O(1)
Use three pointers to reverse the links between nodes.
Recursive Approach
Time: O(n)
Space: O(n) - due to recursion stack
Recursively reverse the rest of the list and reattach the current node.
Algorithm Walkthrough
Example input: nums = [1,2,3,4,5]
Step-by-step execution:
- initial: 1->2->3->4->5
- prev=null, current=1, next=2
- Change 1->next to null: null<-1 2->3->4->5
- prev=1, current=2, next=3
- Change 2->next to 1: null<-1<-2 3->4->5
- prev=2, current=3, next=4
- Change 3->next to 2: null<-1<-2<-3 4->5
- prev=3, current=4, next=5
- Change 4->next to 3: null<-1<-2<-3<-4 5
- prev=4, current=5, next=null
- Change 5->next to 4: null<-1<-2<-3<-4<-5
- prev=5, current=null
- Return prev (5): 5->4->3->2->1