Leetcode 75: Day 3: 206. Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Question:
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?
Solution:
- Maintain three variables (pointers): prev, curr and next.
- At each step of the loop: you need to
- Make the next of curr equal to the prev
- Make prev equal to curr and curr equal to the next.
- If curr becomes null at any point (we don't need the next step), and hence break out of the while loop.
- Make next equal to curr.next
Code:
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) return null;
ListNode prev = null, curr = head, next = curr.next;
while(curr != null){
curr.next = prev;
prev = curr;
curr = next;
if(curr == null) break;
else next = curr.next;
}
return prev;
}
}
Complexity:
- Time: O(N)
- Space: O(1)