Last active
April 6, 2020 05:31
-
-
Save dsapandora/4c8ee1763442035b91f014fb2d2463f9 to your computer and use it in GitHub Desktop.
Reverse a Linked List in groups of given size
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// CPP program to reverse a linked list | |
// in groups of given size | |
#include <bits/stdc++.h> | |
using namespace std; | |
/* Link list node */ | |
class Node | |
{ | |
public: | |
int data; | |
Node* next; | |
}; | |
/* Reverses the linked list in groups | |
of size k and returns the pointer | |
to the new head node. */ | |
Node *reverse (Node *head, int k) | |
{ | |
Node* current = head; | |
Node* next = NULL; | |
Node* prev = NULL; | |
int count = 0; | |
/*reverse first k nodes of the linked list */ | |
while (current != NULL && count < k) | |
{ | |
next = current->next; | |
current->next = prev; | |
prev = current; | |
current = next; | |
count++; | |
} | |
/* next is now a pointer to (k+1)th node | |
Recursively call for the list starting from current. | |
And make rest of the list as next of first node */ | |
if (next != NULL) | |
head->next = reverse(next, k); | |
/* prev is new head of the input list */ | |
return prev; | |
} | |
/* UTILITY FUNCTIONS */ | |
/* Function to push a node */ | |
void push(Node** head_ref, int new_data) | |
{ | |
/* allocate node */ | |
Node* new_node = new Node(); | |
/* put in the data */ | |
new_node->data = new_data; | |
/* link the old list off the new node */ | |
new_node->next = (*head_ref); | |
/* move the head to point to the new node */ | |
(*head_ref) = new_node; | |
} | |
/* Function to print linked list */ | |
void printList(Node *node) | |
{ | |
while (node != NULL) | |
{ | |
cout<<node->data<<" "; | |
node = node->next; | |
} | |
} | |
/* Driver code*/ | |
int main() | |
{ | |
/* Start with the empty list */ | |
Node* head = NULL; | |
/* Created Linked list is 1->2->3->4->5->6->7->8->9 */ | |
push(&head, 9); | |
push(&head, 8); | |
push(&head, 7); | |
push(&head, 6); | |
push(&head, 5); | |
push(&head, 4); | |
push(&head, 3); | |
push(&head, 2); | |
push(&head, 1); | |
cout<<"Given linked list \n"; | |
printList(head); | |
head = reverse(head, 3); | |
cout<<"\nReversed Linked list \n"; | |
printList(head); | |
return(0); | |
} | |
// This code is contributed by rathbhupendra |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Python program to reverse a linked list in group of given size | |
# Node class | |
class Node: | |
# Constructor to initialize the node object | |
def __init__(self, data): | |
self.data = data | |
self.next = None | |
class LinkedList: | |
# Function to initialize head | |
def __init__(self): | |
self.head = None | |
def reverse(self, head, k): | |
current = head | |
next = None | |
prev = None | |
count = 0 | |
# Reverse first k nodes of the linked list | |
while(current is not None and count < k): | |
next = current.next | |
current.next = prev | |
prev = current | |
current = next | |
count += 1 | |
# next is now a pointer to (k+1)th node | |
# recursively call for the list starting | |
# from current. And make rest of the list as | |
# next of first node | |
if next is not None: | |
head.next = self.reverse(next, k) | |
# prev is new head of the input list | |
return prev | |
# Function to insert a new node at the beginning | |
def push(self, new_data): | |
new_node = Node(new_data) | |
new_node.next = self.head | |
self.head = new_node | |
# Utility function to print the linked LinkedList | |
def printList(self): | |
temp = self.head | |
while(temp): | |
print temp.data, | |
temp = temp.next | |
# Driver program | |
llist = LinkedList() | |
llist.push(9) | |
llist.push(8) | |
llist.push(7) | |
llist.push(6) | |
llist.push(5) | |
llist.push(4) | |
llist.push(3) | |
llist.push(2) | |
llist.push(1) | |
print "Given linked list" | |
llist.printList() | |
llist.head = llist.reverse(llist.head, 3) | |
print "\nReversed Linked list" | |
llist.printList() | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be next and pointer to the previous node be prev. See this post for reversing a linked list.
head->next = reverse(next, k) ( Recursively call for rest of the list and link the two sub-lists )
Return prev ( prev becomes the new head of the list
O(n) where n is the number of nodes in the given list.