Reverse a Linked List according to its Size
Given a linked list with n nodes, reverse it in the following way :
- If n is even, reverse it in a group of n/2 nodes.
- If n is odd, keep the middle node as it is, reverse first n/2 elements and reverse last n/2 elements.
Examples:
Input : 1 2 3 4 5 6 (n is even) Output : 3 2 1 6 5 4 Input : 1 2 3 4 5 6 7 (n is odd) Output : 3 2 1 4 7 6 5
Approach: The idea is similar to Reversing a linked list in groups of size k where k is n/2. Just need to check for mid-node.
- If n is even, divide the linked list into two parts i.e. first n/2 elements and last n/2 elements and reverse both the parts.
- If n is odd, divide the linked list into three parts i.e. first n/2 elements, (n/2 + 1) th element and last n/2 elements and reverse both the parts except (n/2 + 1) th element.
Implementation:
C++
// C++ program to reverse given// linked list according to its size#include <bits/stdc++.h>using namespace std;struct Node { int data; Node* next;};// Function to create a new NodeNode* newNode(int data){ Node *temp = new Node; temp->data = data; temp->next = NULL; return temp;}// Prints a list.void printList(Node* head){ Node *temp = head; while (temp) { cout << temp->data << " "; temp = temp->next; } cout << endl;}/* Function to push a Node */void push(Node** head_ref, int new_data){ Node* new_Node = new Node; new_Node->data = new_data; new_Node->next = (*head_ref); (*head_ref) = new_Node;}// Returns size of list.int getSize(Node* head){ Node* curr = head; int count = 0; while (curr) { curr = curr->next; count++; } return count;}// Function to reverse the linked// list according to its sizeNode* reverseSizeBy2Util(Node* head, int k, bool skipMiddle){ if (!head) return NULL; int count = 0; Node* curr = head; Node* prev = NULL; Node* next; // Reverse current block of list. while (curr && count < k) { next = curr->next; curr->next = prev; prev = curr; curr = next; count++; } // If size is even, reverse next block too. if (!skipMiddle) head->next = reverseSizeBy2Util(next, k, false); else { // if size is odd, skip next element // and reverse the block after that. head->next = next; if (next) next->next = reverseSizeBy2Util(next->next, k, true); } return prev;}Node* reverseBySizeBy2(Node* head){ // Get the size of list. int n = getSize(head); // If the size is even, no need // to skip middle Node. if (n % 2 == 0) return reverseSizeBy2Util(head, n/2, false); // If size is odd, middle Node has // to be skipped. else return reverseSizeBy2Util(head, n/2, true);}// Drivers codeint 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 << "Original List : "; printList(head); cout << "Reversed List : "; Node* reversedHead = reverseBySizeBy2(head); printList(reversedHead); return 0;} |
Java
// Java program to reverse given // linked list according to its size class GFG{static class Node{ int data; Node next; }; // Function to create a new Node static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.next = null; return temp; } // Prints a list. static void printList(Node head) { Node temp = head; while (temp != null) { System.out.print( temp.data + " "); temp = temp.next; } System.out.println();} // Function to push a Node static Node push(Node head_ref, int new_data) { Node new_Node = new Node(); new_Node.data = new_data; new_Node.next = (head_ref); (head_ref) = new_Node; return head_ref;} // Returns size of list. static int getSize(Node head) { Node curr = head; int count = 0; while (curr != null) { curr = curr.next; count++; } return count; } // Function to reverse the linked // list according to its size static Node reverseSizeBy2Util(Node head, int k, boolean skipMiddle) { if (head == null) return null; int count = 0; Node curr = head; Node prev = null; Node next=null; // Reverse current block of list. while (curr!=null && count < k) { next = curr.next; curr.next = prev; prev = curr; curr = next; count++; } // If size is even, reverse next block too. if (!skipMiddle) head.next = reverseSizeBy2Util(next, k, false); else { // if size is odd, skip next element // and reverse the block after that. head.next = next; if (next != null) next.next = reverseSizeBy2Util(next.next, k, true); } return prev; } static Node reverseBySizeBy2(Node head) { // Get the size of list. int n = getSize(head); // If the size is even, no need // to skip middle Node. if (n % 2 == 0) return reverseSizeBy2Util(head, n/2, false); // If size is odd, middle Node has // to be skipped. else return reverseSizeBy2Util(head, n/2, true); } // Driver code public static void main(String args[]) { // Start with the empty list / Node head = null; // Created Linked list is 1.2.3.4.5.6.7.8.9 / head = push(head, 9); head = 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); System.out.print( "Original List : "); printList(head); System.out.print( "Reversed List : "); Node reversedHead = reverseBySizeBy2(head); printList(reversedHead); }}// This code is contributed by Arnab Kundu |
Python3
# Python3 program to reverse given # linked list according to its size class Node: def __init__(self, data): self.data = data self.next = None# Prints a list. def printList(head): temp = head while temp: print(temp.data, end = " ") temp = temp.next print()# Function to push a Node def push(head_ref, new_data): new_Node = Node(new_data) new_Node.next = head_ref head_ref = new_Node return head_ref# Returns size of list. def getSize(head): curr = head count = 0 while curr: curr = curr.next count += 1 return count # Function to reverse the linked # list according to its size def reverseSizeBy2Util(head, k, skipMiddle): if not head: return None count = 0 curr, prev, next = head, None, None # Reverse current block of list. while curr and count < k: next = curr.next curr.next = prev prev = curr curr = next count += 1 # If size is even, reverse next block too. if not skipMiddle: head.next = reverseSizeBy2Util(next, k, False) else: # if size is odd, skip next element # and reverse the block after that. head.next = next if next: next.next = reverseSizeBy2Util(next.next, k, True) return prev def reverseBySizeBy2(head): # Get the size of list. n = getSize(head) # If the size is even, no # need to skip middle Node. if n % 2 == 0: return reverseSizeBy2Util(head, n//2, False) # If size is odd, middle # Node has to be skipped. else: return reverseSizeBy2Util(head, n//2, True) # Drivers code if __name__ == "__main__": # Start with the empty list head = None # Created Linked list is 1.2.3.4.5.6.7.8.9 head = push(head, 9) head = 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) print("Original List : ", end = "") printList(head) print("Reversed List : ", end = "") reversedHead = reverseBySizeBy2(head) printList(reversedHead) # This code is contributed by Rituraj Jain |
C#
// C# program to reverse given // linked list according to its size using System; class GFG{public class Node{ public int data; public Node next; }; // Function to create a new Node static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.next = null; return temp; } // Prints a list. static void printList(Node head) { Node temp = head; while (temp != null) { Console.Write( temp.data + " "); temp = temp.next; } Console.WriteLine();} // Function to push a Node static Node push(Node head_ref, int new_data) { Node new_Node = new Node(); new_Node.data = new_data; new_Node.next = (head_ref); (head_ref) = new_Node; return head_ref;} // Returns size of list. static int getSize(Node head) { Node curr = head; int count = 0; while (curr != null) { curr = curr.next; count++; } return count; } // Function to reverse the linked // list according to its size static Node reverseSizeBy2Util(Node head, int k, Boolean skipMiddle) { if (head == null) return null; int count = 0; Node curr = head; Node prev = null; Node next=null; // Reverse current block of list. while (curr!=null && count < k) { next = curr.next; curr.next = prev; prev = curr; curr = next; count++; } // If size is even, reverse next block too. if (!skipMiddle) head.next = reverseSizeBy2Util(next, k, false); else { // if size is odd, skip next element // and reverse the block after that. head.next = next; if (next != null) next.next = reverseSizeBy2Util(next.next, k, true); } return prev; } static Node reverseBySizeBy2(Node head) { // Get the size of list. int n = getSize(head); // If the size is even, no need // to skip middle Node. if (n % 2 == 0) return reverseSizeBy2Util(head, n/2, false); // If size is odd, middle Node has // to be skipped. else return reverseSizeBy2Util(head, n/2, true); } // Driver code public static void Main(String []args) { // Start with the empty list / Node head = null; // Created Linked list is 1.2.3.4.5.6.7.8.9 / head = push(head, 9); head = 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); Console.Write( "Original List : "); printList(head); Console.Write( "Reversed List : "); Node reversedHead = reverseBySizeBy2(head); printList(reversedHead); }}// This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to reverse given // linked list according to its size class Node { constructor() { this.data = 0; this.next = null; } } // Function to create a new Node function newNode(data) { var temp = new Node(); temp.data = data; temp.next = null; return temp; } // Prints a list. function printList(head) { var temp = head; while (temp != null) { document.write(temp.data + " "); temp = temp.next; } document.write("<br>"); } // Function to push a Node function push(head_ref, new_data) { var new_Node = new Node(); new_Node.data = new_data; new_Node.next = head_ref; head_ref = new_Node; return head_ref; } // Returns size of list. function getSize(head) { var curr = head; var count = 0; while (curr != null) { curr = curr.next; count++; } return count; } // Function to reverse the linked // list according to its size function reverseSizeBy2Util(head, k, skipMiddle) { if (head == null) return null; var count = 0; var curr = head; var prev = null; var next = null; // Reverse current block of list. while (curr != null && count < k) { next = curr.next; curr.next = prev; prev = curr; curr = next; count++; } // If size is even, reverse next block too. if (!skipMiddle) head.next = reverseSizeBy2Util(next, k, false); else { // if size is odd, skip next element // and reverse the block after that. head.next = next; if (next != null) next.next = reverseSizeBy2Util(next.next, k, true); } return prev; } function reverseBySizeBy2(head) { // Get the size of list. var n = getSize(head); // If the size is even, no need // to skip middle Node. if (n % 2 == 0) return reverseSizeBy2Util(head, parseInt(n / 2), false); // If size is odd, middle Node has // to be skipped. else return reverseSizeBy2Util(head, parseInt(n / 2), true); } // Driver code // Start with the empty list / var head = null; // Created Linked list is 1.2.3.4.5.6.7.8.9 / head = push(head, 9); head = 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); document.write("Original List : "); printList(head); document.write("Reversed List : "); var reversedHead = reverseBySizeBy2(head); printList(reversedHead); </script> |
Output
Original List : 1 2 3 4 5 6 7 8 9 Reversed List : 4 3 2 1 5 9 8 7 6
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
