Description
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?
Approach - Iteration
- Take 2 Nodes one for previous and one for current and loop an with the use of temp Node change the links
Time: O(n) Space: O(1)- We iterate through the n nodes and only use constant space
- Standard way what we need to change we store first then we change it to new value then we just push both nodes one ahead
- Check if recursive solution is really required
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode tmp = curr.next;
curr.next = prev;
prev = curr;
curr = tmp;
}
return prev;
}
}