206. Reverse Linked List
Reverse Linked List
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 1) Iterative
Idea:
A two pointer approach can be employed to traverse the linked list and simultaneously reserving the pointers.
First of all, for corner cases viz. zero and one element return directly the head as the list contains less than two elements.
Further, traverse the list with the help of two pointers, p and q, where p initially points to the first element and q points to the second element.
At each step, we reverse the pointer between these two nodes q->next becomes p and then go to the next two nodes p becomes q and q becomes the next element.
Let`s Code It!
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if(head==null || head.next==null){
return head;
}
let p = head ,q = head.next;
head.next = null;
while(q!=null){
let temp = q;
q = q.next;
temp.next = p;
p = temp;
}
return p;
};/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if(head==null || head.next==null){
return head;
}
let prev = null;
while (head) {
let next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
};
Time Complexity
We are travse the linked list only once, hence the time complexity will be O(n).
Space Complexity
We are using constant space, hence space complexity will be O(1).
Let's say the list is 1->2->3:
Recursion: reverseList(1) -> reverseList(2) -> reverseList(3)
reverseList(3) returns "3"
Then, in the function reverseList(2) function: head is 2. head->next is 3. So head->next->next = head implies 3->next = 2 hence reversing the arrow. head->next= NULL so 2->next = NULL. Now, our list is 1->2<-3
reverseList(2) returns "3" (temp)
Then, in the function reverseList(1): head is 1. head->next is 2. So head->next->next = head imples 2->next = 1 hence reversing the arrow. head->next = NULL implies 1->next = NULL. Now, our list is reversed! 1<-2<-3
reverseList(1) returns "3" (temp) which is the head of our new list./**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if (!head || !head.next)
return head;
let newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
};Time Complexity
We are travse the linked list only once, hence the time complexity will be O(n).
Space Complexity
We are using newHead extra space, hence space complexity will be O(n).
That’s all folks! In this post, we solved LeetCode problem #206. Reverse Linked List
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.
In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!
Comments
Post a Comment