L21. Reverse Nodes in K Group Size of LinkedList
Vložit
- čas přidán 28. 11. 2023
- Problem Link: tinyurl.com/4dbz8fnn
Entire LL Sheet: takeuforward.org/linked-list/...
Check our A2Z DSA Course: takeuforward.org/strivers-a2z...
Please do give us a like, and subscribe to us if you are new to our channel.
Do follow us on our socials: linktr.ee/takeuforward
This question solution was already given by striver in past, but this latest one is very clear and easily understandable. This is a very good thing about him that he always upgrades his art of teaching and his content as well.
Yes. It is not about making a cookie cutter video to gain views. A lot of research goes in the production of these videos, mainly in planning the best and easiest approach for the viewer. The content is highly curated and the logic builds on preceeding videos. The man is a very good teacher who happens to know the subject really well.
What a fantastic explanation by breaking the problem into subparts!!!💥
Superb Explanation!! Didn't understood in the first watch but got it while watching for the second time!!
I was able to write almost the same code by myself thanks Striver!
just after listening once i had code the solution in one go and it executed perfectly.... great explanation by striver
You can also solve this question using recursion:
Step 1: Base Case -> if LL is empty return null
Step 2: Check do we even have k nodes to reverse if not you can return head(teh node itself).
Step 3: Just reverse the first k group nodes and then leave everything on recursion.
Step 4: return the head of the first LL that you have reversed.
Below is the detailed code of c++:
Code:
ListNode* reverseKGroup(ListNode* head, int k) {
// Recursive solution
// Base Case
if (head == nullptr) {
return nullptr;
}
// step 1: Check if there are at least k nodes to reverse
ListNode* temp = head;
int count = 0;
while (temp != nullptr && count < k) {
temp = temp->next;
count++;
}
// If there are fewer than k nodes left, return head without reversing
if (count < k) {
return head;
}
// Step 2 : reverse k nodes
ListNode* prev = nullptr;
temp = head;
ListNode* next = nullptr;
count = 0;
while (temp != nullptr && count < k) {
next = temp->next;
temp->next = prev;
prev = temp;
temp = next;
count++;
}
// recursive call;
if (next != nullptr) {
head->next = reverseKGroup(next, k);
}
// return
return prev;
}
TC -> O(N)
Sc -> O(N) -> recursive call stack memory
thanku
You made it look so easy. Absolutely FAB!
understood bhaiya !! Amazing explaination
Mza aagya bhaiya!!
suoerb explanation
Amazing explanation.
superb explanation
amazing explanation
Best explanation ❤
great video
wonderful solution
'
DAY42:Got the intuition before starting this video
😅failled in edgecase
We can also use dummyNode and at last return dummyNode->next
Thank you Bhaiya
Understood✅🔥🔥
Understood ❤
Thank you sir.
Bro stack and queue next 😢
Already hai bhai
well explained
Thanku ji
superb
Thanks for the great explanation Striver.
Have one query at 21:14
Even if we do not add if(prevNode != null), just "prevNode.next = temp" would also work fine.
In that case null node will be pointing to head but that is fine, since we are returning head.
If prevNode is NULL, then prevNode->next will be NULL->next,.... That will eventually throw NULL POINTER EXCEPTION
Understooood
this got to be the hardest linked list question
Recursion se socho. It's not that difficult if solved recursively
hey can we expect strings / bit manipulation as next plz
Heaps also
UNDERSTOOOD
explained 100x times better than leetcode yt channel
yes pleaseeee striver bhaiyaa we need bit manipulation and strings as next playlist pleasssse bhaiyaa
Okay spoonfeeder😂
with dummy node approach we will not have to remember previous nodes
node * reverseKGroup(node * head, int k) {
node * dummy = new node(-1, head);
node * start = dummy, * end= nullptr;
while(start->next != nullptr)
{
end = start->next;
int n = k-1;
while(end->next != nullptr && n--) //finding end
end = end->next;
if(n > 0) break; //if group cant be formed break out
node * nextnode = end->next, * t = start->next; //remembering start, and preserving the next node
end->next = nullptr; //breaking list
node * temp = reverse(start->next); //reverse the LL using recursion
t->next = nextnode; //joining the starting node to next node to the next node
start->next = temp; //connecting with previous nodes
start = t; //moving the start to end of current group
}
return dummy->next;
}
understood
Understood
This is much complex implementation. Using recursion it can be done much easier way
. Just reverse first three and call solve function again on rest or linked list. Base condition will be when list is exhausted or length is less than k.
Agree!
I did it recursively.
class Solution:
# returns first node and last node of the revered list
def reverse(self, head):
if head == None: return None
prev = None
current = head
while current:
nxt = current.next
current.next = prev
prev = current
current = nxt
return (prev, head)
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head: return head
kBackup = k
newHead = head
start = head
while head:
if k==1: # kth node found
newHead = head
nextListStart = head.next
head.next = None # break the link
first, last = self.reverse(start)
last.next = self.reverseKGroup(nextListStart, kBackup) # recursively call for remaining list
k-=1
head = head.next
return newHead
There is a slight problem in the code where prevLast is not able to connect with nextNode. I've introduced a newHead variable to store the head of the reversed group. Also, I added temp->next = nextNode; after reversing the linked list to connect the reversed group to the nextNode.
while (temp != nullptr) {
ListNode *kthNode = getKthNode(temp, k);
if (kthNode == nullptr) {
break;
}
ListNode *nextNode = kthNode->next;
kthNode->next = nullptr;
ListNode *newHead = reverseLL(temp);
if (temp == head) {
head = newHead;
}
else {
prevNode->next = newHead;
}
temp->next = nextNode;
prevNode = temp;
temp = nextNode;
}
Thanks for this amazing video. I tried it in copy and saw links missing so made little changes so that links can be connected. Again thanks.
your code not working
Can be done by recursion(which is easier than striver's method - his is too messy)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKsteps(ListNode* node, int k){
//reverse the LL starting from node till k steps
if(k == 1) return node;
ListNode* prev = NULL;
ListNode* curr = node;
ListNode* next = node->next;
ListNode* newHead;
while(k--){
curr->next = prev;
prev = curr;
curr = next;
if(next) next = next->next;
}
newHead = prev;
return newHead;
}
ListNode* solve(ListNode* node, int k){
if(node == NULL) return node;
int x = k;
ListNode* temp = node;
while(x--){
if(temp == NULL) return node;
temp = temp->next;
}
ListNode* headToBeJoined = solve(temp, k);
ListNode* parentTail = node;
ListNode* parentHead = reverseKsteps(node, k);
parentTail->next = headToBeJoined;
return parentHead;
}
ListNode* reverseKGroup(ListNode* head, int k) {
return solve(head, k);
}
};
❤❤❤
if(head==null) return head;
Node prev=null,cur=head,next=null;
int cnt=0;
while(cur!=null&&cnt
It’s not always about writing the shortest code. A readable and self explanatory code is always preferred. Cheers!
@@takeUforward owned that laughing fella
ur solution is not space optimized as recursion has call stack which can consume memory
I have already tried this code in code studio and it was not working ...it seems he has copied from love babbar ...he has also done the same thing but has missed some parameters
bro add this to playlist please
Should have also added the recursive O(k) stack space solution here. That is a bit easier to come up with.
In worst case it will be 0(n)
Your eyes 👀 became too weak
take care man
Loved it.
I did it recursively as it was much easier for me to understand.
class Solution:
# returns first node and last node of the revered list
def reverse(self, head):
if head == None: return None
prev = None
current = head
while current:
nxt = current.next
current.next = prev
prev = current
current = nxt
return (prev, head)
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head: return head
kBackup = k
newHead = head
start = head
while head:
if k==1: # kth node found
newHead = head
nextListStart = head.next
head.next = None # break the link
first, last = self.reverse(start)
last.next = self.reverseKGroup(nextListStart, kBackup) # recursively call for remaining list
k-=1
head = head.next
return newHead
Please Striver provide iterative approach Pyhton code for this problem I have tried lot many times but none of my test cases are getting passed.
Next strings plsss
Time complexity in worst case will be O(N^2). consider a case when K =1, the inner loops will go through every node and the outer loops will go through every element individually as well. So, overall tc is O(N^2). How come nobody is the comment section except one student is asking about it ?
BRO U DIDN'T UNDERSTAND THE CONCEPT IT WILL ALWAYS BE O(2N) NOT MORE THAN THAT EVEN K=1 THEN REVERSE WILL DIRECTLY RETURN THE HEAD WHICH WILL BE ONE LOOP AND OVERALL WE WILL TRAVERSE TO THE GIVEN LINKED LIST WHICH IS O(N)
@@maverick_8707 bro please explain the tc i didn't understood
one is for finding the kth node which we can take O(k) and then reverse which also we can take O(k) and what about the outer while loop it will also run for k times no
?
1st comment bhaiya
I have used recursion.
```
Node *helper(Node *root, int k) {
if(root == NULL || root->next == NULL) return root;
int count = 0;
Node *curr = root, *prev = NULL, *nxt = NULL;
while(count != k && curr != NULL) {
curr = curr->next;
count++;
}
if(count < k) return root;
curr = root;
count = 0;
while(count < k && curr != NULL) {
nxt = curr->next;
curr->next = prev;
prev = curr;
curr = nxt;
count++;
}
Node *temp = helper(nxt, k);
root->next = temp;
return prev;
}
```
Impressive and easy to understand
Isn't this TC O(N^2) because of outer loop traversing the whole linked list & inner functions traversing sections of linked list ?
yes it will be.
@@saswatrath4646 not n^2 but k^2
The last group of linked list(last part where we don't have kth node) is not getting reversed, tried with different approaches as well.
Its working now, thanks
class Solution
{
public static Node reverse(Node head, int k)
{
//Your code here
Node temp = head;
Node prevNode = null;
while(temp != null)
{
Node kthNode = findKthNode(temp, k);
if(kthNode == null)
{
temp = ReverseGroup(temp);
if(prevNode != null) prevNode.next = temp;
break;
}
Node nextNode = kthNode.next;
kthNode.next = null;
Node newNode = ReverseGroup(temp);
if(temp == head)
{
head = newNode;
} else {
prevNode.next = kthNode;
}
prevNode = temp;
temp = nextNode;
}
return head;
}
public static Node findKthNode(Node head, int k)
{
Node temp = head;
if(temp == null || temp.next == null)
return temp;
while(temp != null && k > 1)
{
temp = temp.next;
k--;
}
return temp;
}
public static Node ReverseGroup(Node head)
{
Node temp = head;
if(temp == null || temp.next == null)
return temp;
Node last = null;
Node temp1 = head.next;
//reverse the linked list till n-1
while(head.next != null){
head.next = last;
last = head;
head = temp1;
temp1 = temp1.next;
}
//last node pointer change
head.next = last;
last = head;
return last;
}
}
Striver Make Strings Playlist Please ......
Confusion
prevlast is a pointer toh usme hum prevlast->next = Kthnode kaise store karwa sakte hai??
It is not a pointer,it is node which is initiated as null or head...And while traveling we are assigning prevNode to temp and incrementing temp...
using recursion it would be easy
Main while loop will not take any time sir ?
That's what i didn't get. The TC is O(3*n), if the main while loop complexity is considered
The Sheet link is not working
Please fix it.
Why we used k-=1 while finding getkthnode method
We start with k and decrement it at each step while traversing the list. It's like a count down to reach the Kth node
@@rushhour4379 no but there is one k-=1 before the loop
My solution is not working, and the solution given in the sheet is different. For ex => head = [1,2,3,4,5], k = 2, I'm getting [2,1,5]. PLZ help!
class Solution {
public:
ListNode* reverseLinkedList(ListNode *head)
{
ListNode* temp = head;
ListNode* prev = NULL;
while(temp != NULL) {
ListNode* front = temp->next;
temp->next = prev;
prev = temp;
temp = front;
}
return prev;
}
private:
ListNode* getKthNode(ListNode* temp, int k) {
k -= 1;
while(temp != NULL && k > 0) {
k--;
temp = temp->next;
}
return temp;
}
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* temp = head;
ListNode* prevLast = NULL;
while(temp != NULL) {
ListNode* kThNode = getKthNode(temp, k);
if(kThNode == NULL) break;
ListNode* nextHead = kThNode->next;
kThNode->next = NULL;
ListNode* newHeadOfKGroup = reverseLinkedList(temp);
if(temp == head) {
head = newHeadOfKGroup;
}
else {
prevLast->next = newHeadOfKGroup;
}
prevLast = temp;
temp = nextHead;
}
if(prevLast != NULL) prevLast->next = temp;
return head;
}
};
god
Excellent explanation.
The following solution reduces worst time complexity to O(n+k):
pair reverseK(Node* head, int k)
{
Node* p = NULL;
Node* q = head;
int count = k;
while (count > 0 && q)
{
count--;
Node*r = q->next;
q->next = p;
p = q;
q = r;
}
if (count > 0)
return reverseK(p, k-count);
return {p, q};
}
Node* reverseKGroup(Node* head, int k)
{
Node* dummyNode = new Node(-1, head);
Node* prevTail = dummyNode;
Node* kHead = dummyNode->next;
while (kHead)
{
pair p = reverseK(kHead, k);
prevTail-> next = p.first;
prevTail = kHead;
kHead = p.second;
}
Node* ans = dummyNode->next;
delete dummyNode;
return ans;
}
class Solution
{
public:
ListNode *reverse(ListNode *&head)
{
ListNode *temp = head;
ListNode *put = nullptr;
while (temp)
{
ListNode *h = temp->next;
temp->next = put;
put = temp;
temp = h;
}
return put;
}
ListNode *reverseKGroup(ListNode *head, int k)
{
if (k == 1)
return head;
int i = 1;
ListNode *temp = head, *start = head, *pre = nullptr, *ans = nullptr;
bool chk = 1;
while (temp)
{
if (i == k)
{
ListNode *upcoming = temp->next;
temp->next = nullptr;
ListNode *coming = reverse(start);
ListNode *it = coming;
if (!pre)
ans = coming;
else
pre->next = coming;
while (it->next)
it = it->next;
it->next = upcoming;
i = 1;
start = upcoming;
temp = upcoming;
pre = it;
}
else
{
i++;
temp = temp->next;
}
}
return ans;
}
};
My solution , I wrote it straightforward here second is start and temp will move ,Hope it helps
class Solution {
public:
ListNode* reverseLL(ListNode* head)
{
if(head==NULL || head->next==NULL)
return head;
ListNode*prev=NULL;
ListNode*temp=head;
while(temp)
{
ListNode*store=temp->next;
temp->next=prev;
prev=temp;
temp=store;
}
return prev;
}
ListNode* reverseKGroup(ListNode* head, int k) {
if(head==NULL || head->next==NULL)
return head;
ListNode*temp=head;
ListNode*second=head;
ListNode*prev=NULL;
ListNode*next=NULL;
int count=0;
while(temp!=NULL)
{
count++;
if(count==k)
{
next= temp->next;
temp->next=NULL;
temp=reverseLL(second);
if(second==head)
{
head=temp;
}
else
{
prev->next=temp;
}
prev=second;
temp=next;
second=next;
count=0;
continue;
}
temp=temp->next;
}
if(countnext=next;
return head;
}
};
Please provide Java code. My code is giving TLE during submission.
JAVA SOLUTION :
public ListNode reverseKGroup(ListNode head, int k) {
ListNode temp = head;
ListNode previous = null;
while(temp!=null){
ListNode kthNode= findKthNode(temp, k);
if(kthNode==null){
if(previous!=null){
previous.next= temp;
}
break;
}
ListNode nextNode=kthNode.next;
kthNode.next=null;
// ListNode newHead=reverse(temp);
reverse(temp);
if(head==temp){
head= kthNode;
//head = newHead;
} else{
previous.next=kthNode;
//previous.next = newHead;
}
//temp.next= nextNode;
previous = temp;
temp = nextNode;
}
return head;
}
private ListNode findKthNode(ListNode temp, int k){
k=k-1;
while(temp!=null && k>0){
temp=temp.next;
k--;
}
return temp;
}
private ListNode reverse(ListNode temp){
ListNode prev= null;
ListNode cur=temp;
while(cur!=null){
ListNode next = cur.next;
cur.next=prev;
prev=cur;
cur=next;
}
return prev;
}
Only one test case is still not passing
def reverse_ll(head):
prev = None
curr = head
next_node = None
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
def get_kth_node(temp, k):
k -= 1
while temp and k > 0:
k -= 1
temp = temp.next
return temp
def kReverse(head, k):
temp = head
prev_last = None
next_node = None
while temp:
kth_node = get_kth_node(temp, k)
if not kth_node:
if prev_last:
prev_last.next = temp
break
next_node = kth_node.next
kth_node.next = None
reverse_ll(temp)
if temp == head:
head = kth_node
else:
if prev_last:
prev_last.next = kth_node
prev_last = temp
temp = next_node
return head
class Solution {
public:
ListNode* reverseLinkedList(ListNode *head)
{
ListNode* temp = head;
ListNode* prev = NULL;
while(temp != NULL) {
ListNode* front = temp->next;
temp->next = prev;
prev = temp;
temp = front;
}
return prev;
}
private:
ListNode* getKthNode(ListNode* temp, int k) {
k -= 1;
while(temp != NULL && k > 0) {
k--;
temp = temp->next;
}
return temp;
}
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* temp = head;
ListNode* prevLast = NULL;
while(temp != NULL) {
ListNode* kThNode = getKthNode(temp, k);
if(kThNode == NULL) break;
ListNode* nextHead = kThNode->next;
kThNode->next = NULL;
ListNode* newHeadOfKGroup = reverseLinkedList(temp);
if(temp == head) {
head = newHeadOfKGroup;
}
else {
prevLast->next = newHeadOfKGroup;
}
prevLast = temp;
temp = nextHead;
}
if(prevLast != NULL) prevLast->next = temp;
return head;
}
};
can't we do it with dummy? create the whole chain again simple
JAVA Solution :
public ListNode reverseKGroup(ListNode head, int k) {
ListNode temp = head;
ListNode previous = null;
while(temp!=null){
ListNode kthNode= findKthNode(temp, k);
if(kthNode==null){
if(previous!=null){
previous.next= temp;
}
break;
}
ListNode nextNode=kthNode.next;
kthNode.next=null;
// ListNode newHead=reverse(temp);
reverse(temp);
if(head==temp){
head= kthNode;
//head = newHead;
} else{
previous.next=kthNode;
//previous.next = newHead;
}
//temp.next= nextNode;
previous = temp;
temp = nextNode;
}
return head;
}
private ListNode findKthNode(ListNode temp, int k){
k=k-1;
while(temp!=null && k>0){
temp=temp.next;
k--;
}
return temp;
}
private ListNode reverse(ListNode temp){
ListNode prev= null;
ListNode cur=temp;
while(cur!=null){
ListNode next = cur.next;
cur.next=prev;
prev=cur;
cur=next;
}
return prev;
}
recursive solution
class Solution {
public:
int count(ListNode* head) {
int bcount = 0;
while (head != nullptr) {
bcount++;
head = head->next;
}
return bcount;
}
ListNode* reverseKGroup(ListNode* head, int k) {
// basecase
if (count(head) < k || head == nullptr || head->next == nullptr) {
return head;
}
int cnt = 0;
ListNode* prev = nullptr;
ListNode* temp = head;
ListNode* next = NULL;
while (temp != nullptr && cnt < k) {
next = temp->next;
temp->next = prev;
prev = temp;
temp = next;
cnt++;
}
// new head is prev
head->next = reverseKGroup(next, k);
return prev;
}
};
us
i have done this q by recursion
Node* rev(Node* head){
if(head==NULL|| head->next==NULL)return head;
Node* front=NULL;
Node* prev=NULL;
Node* temp=head;
while(temp!=NULL){
front=temp->next;
temp->next=prev;
prev=temp;
temp=front;
}
return prev;
}
Node* kReverse(Node* head, int k) {
// Write your code here.
if(k==1 || head==NULL)return head;
int cnt=0;
Node* temp=head;
while(temp!=NULL){
cnt++;
if(cnt==k)break;
temp=temp->next;
if(temp==NULL && cntnext,k);
temp->next=NULL;
Node* newhead=rev(head);
Node* newtemp=newhead;
while(newtemp->next!=NULL){
newtemp=newtemp->next;
}
newtemp->next=nextnewhead;
return newhead;
}
It is not correct about the TC. It is O(N**2) not O(N).
You are wrong about that.
He is correct 💯
O(2n)
After normalisation
On)
Sorry to say, but this time you didn't explained well 😢
Understood
Understood
Understood