Given a linked list, write a function to reverse every k node (where k is an input to the function). Examples:
Inputs: 1->2->3->4->5->6->7->8->NULL, k = 3
Output: 3->2->1->6->5->4->8->7->NULLInputs: 1->2->3->4->5->6->7->8->NULL, k = 5
Output: 5->4->3->2->1->8->7->6->NULL
Multiple approaches for the above problem have been already discussed in the posts below:
- Reverse a Linked List in groups of given size | Set 1 -> Use recursion with O(n/k) extra space
- Reverse a Linked List in groups of given size | Set 2 -> Use stack with O(k) extra space
- Reverse a singly Linked List in groups of given size | Set 3 -> Use deque with O(k) extra space
Approach: This article focus on an approach that uses O(1) auxiliary space. Below are the steps to follow:
- Keep track of the first node in a pointer for each group of k elements in the linked list.
- Reverse the order of the next k elements from the first node of the current group using this algorithm.
- After reversing, the first node of the current group will become the last node. Connect it with the k+1th node of the linked list.
- The k+1th node will become the first node of the next group of k elements. Similarly, repeat the process for every group of k elements till the whole linked list has been traversed.
Below is the implementation of the above approach:
C++
// C++ program to reverse a linked// list in groups of given size#include <bits/stdc++.h>using namespace std; // Linked list Node class Node { public: int data; Node* next; Node(int d) { data = d; next = NULL; } }; void reverse(Node** node, int k) { if (k == 1) return; // Keeps track of the final list Node* result = NULL; // Append a new node at initial step Node* head = new Node(0); head->next = *(node); Node* next = (*node)->next; int count = 0; while (next) { count++; // Update the pointer and // iterate linked list by // using node & next pointer Node* tmp = next->next; next->next = *(node); *(node) = next; next = tmp; if (count == k - 1) { count = 0; if (result == NULL) result = *(node); // Last step to join the // reversed k-group with // the linked list tmp = head->next; tmp->next = next; head->next = *(node); head = tmp; // Move on to the next k-group *(node) = next; if (*(node)!= NULL) next = (*node)->next; } } // Process last elements Node* tmp = head->next; if (tmp) tmp->next = NULL; head->next = *(node); *(node) = result; return; } // Utility functions // Function to inserts a new // Node at front of the list void push(Node** head,int new_data) { Node* new_node = new Node(new_data); new_node->next = *(head); *(head) = new_node; } // Function to print linked list void printList(Node** head) { Node* temp = *(head); while (temp) { cout << temp->data << " "; temp = temp->next; } cout << endl; }/* Driver program to test above functions */int main(){ Node* head = NULL; /* Constructed Linked List is * 1->2->3->4->5->6->7->8->null */ push(&head,8); push(&head,7); push(&head,6); push(&head,5); push(&head,4); push(&head,3); push(&head,2); push(&head,1); reverse(&head, 3); printList(&head); return 0;}// This code is contributed by maddler. |
Java
// Java program to reverse a linked// list in groups of given sizeclass LinkedList { // head of list Node head; // Linked list Node class Node { int data; Node next; Node(int d) { data = d; next = null; } } Node reverse(Node node, int k) { if (k == 1) return node; // Keeps track of the final list Node result = null; // Append a new node at initial step Node head = new Node(0); head.next = node; Node next = node.next; int count = 0; while (next != null) { count++; // Update the pointer and // iterate linked list by // using node & next pointer Node tmp = next.next; next.next = node; node = next; next = tmp; if (count == k - 1) { count = 0; if (result == null) result = node; // Last step to join the // reversed k-group with // the linked list tmp = head.next; tmp.next = next; head.next = node; head = tmp; // Move on to the next k-group node = next; if (node != null) next = node.next; } } // Process last elements Node tmp = head.next; if (tmp != null) tmp.next = null; head.next = node; return result; } // Utility functions // Function to inserts a new // Node at front of the list public void push(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } // Function to print linked list void printList() { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } /* Driver program to test above functions */ public static void main(String args[]) { LinkedList llist = new LinkedList(); /* Constructed Linked List is * 1->2->3->4->5->6->7->8->null */ llist.push(8); llist.push(7); llist.push(6); llist.push(5); llist.push(4); llist.push(3); llist.push(2); llist.push(1); llist.head = llist.reverse(llist.head, 3); llist.printList(); }} |
Python3
# Python program to reverse a linked# list in groups of given size# Node classclass Node: # Function to initialize the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize # next as nulldef reverse(head, k): temp = jump = Node(0) temp.next = left = right = head while True: count = 0 while right and count < k: # use right to locate the range right = right.next count += 1 if count == k: # if size k satisfied, reverse the inner linked list pre, cur = right, left for _ in range(k): cur.next, cur, pre = pre, cur.next, cur # standard reversing jump.next, jump, left = pre, left, right # connect two k-groups else: return temp.next# Utility functions# Function to inserts a new# Node at front of the listdef push(head, new_data): new_node = Node(new_data) new_node.next = head head = new_node return head# Function to print linked listdef printList(head): temp = head while(temp): print(temp.data) temp = temp.next# Driver program to test above functionshead = None# Constructed Linked List is# 1->2->3->4->5->6->7->8->nullhead = push(head, 8)head = push(head, 7)head = push(head, 6)head = push(head, 5)head = push(head, 4)head = push(head, 3)head = push(head, 2)head = push(head, 1)head = reverse(head, 3)printList(head)# This code is contributed by rj13to. |
C#
using System;// C# program to reverse a linked// list in groups of given sizepublic class List { // head of list public Node head; // Linked list Node public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } Node reverse(Node node, int k) { if (k == 1) return node; // Keeps track of the readonly list Node result = null; // Append a new node at initial step Node head = new Node(0); head.next = node; Node next = node.next; int count = 0; while (next != null) { count++; // Update the pointer and // iterate linked list by // using node & next pointer Node tmp1 = next.next; next.next = node; node = next; next = tmp1; if (count == k - 1) { count = 0; if (result == null) result = node; // Last step to join the // reversed k-group with // the linked list tmp1 = head.next; tmp1.next = next; head.next = node; head = tmp1; // Move on to the next k-group node = next; if (node != null) next = node.next; } } // Process last elements Node tmp = head.next; if (tmp != null) tmp.next = null; head.next = node; return result; } // Utility functions // Function to inserts a new // Node at front of the list public void Push(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } // Function to print linked list void printList() { Node temp = head; while (temp != null) { Console.Write(temp.data + " "); temp = temp.next; } Console.WriteLine(); } /* Driver program to test above functions */ public static void Main(String []args) { List llist = new List(); /* * Constructed Linked List is 1->2->3->4->5->6->7->8->null */ llist.Push(8); llist.Push(7); llist.Push(6); llist.Push(5); llist.Push(4); llist.Push(3); llist.Push(2); llist.Push(1); llist.head = llist.reverse(llist.head, 3); llist.printList(); }}// This code is contributed by gauravrajput1 |
Javascript
<script>// javascript program to reverse a linked// list in groups of given size // head of list var head; // Linked list Node class Node { constructor(val) { this.data = val; this.next = null; } } function reverse(node , k) { if (k == 1) return node; // Keeps track of the final list var result = null; // Append a new node at initial step var head = new Node(0); head.next = node; var next = node.next; var count = 0; while (next != null) { count++; // Update the pointer and // iterate linked list by // using node & next pointer var tmp = next.next; next.next = node; node = next; next = tmp; if (count == k - 1) { count = 0; if (result == null) result = node; // Last step to join the // reversed k-group with // the linked list tmp = head.next; tmp.next = next; head.next = node; head = tmp; // Move on to the next k-group node = next; if (node != null) next = node.next; } } // Process last elements var tmp = head.next; if (tmp != null) tmp.next = null; head.next = node; return result; } // Utility functions // Function to inserts a new // Node at front of the list function push(new_data) {var new_node = new Node(new_data); new_node.next = head; head = new_node; } // Function to print linked list function printList() {var temp = head; while (temp != null) { document.write(temp.data + " "); temp = temp.next; } document.write(); } /* Driver program to test above functions */ /* * Constructed Linked List is 1->2->3->4->5->6->7->8->null */ push(8); push(7); push(6); push(5); push(4); push(3); push(2); push(1); head = reverse(head, 3); printList();// This code is contributed by gauravrajput1</script> |
Output
3 2 1 6 5 4 8 7
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Read More to that Topic: geeksforgeeks.org/reverse-a-singly-linked-list-in-groups-of-given-size-set-4-space-efficient-approach/ […]