Given a Linked List which represents a sentence S such that each node represents a letter, the task is to reverse the sentence without reversing individual words.
For example, for a given sentence “I love Geeks for Geeks”, the Linked List representation is given as:
I-> ->l->o->v->e-> ->G->e->e->k->s-> ->f->o->r-> ->G->e->e->k->s
Examples:
Input: I love Geeks for Geeks
Output: Geeks for Geeks love IInput: practice makes a man perfect
Output: perfect man a makes practice
Approach: The idea is to navigate the linked list from the beginning. Every time space is encountered, swap the space to the beginning of that word. Repeat this step until the last node is reached. Finally set the first words last letter to point null which will become the last node and keep changing the pointers.
Below is the implementation of the approach:
C++
#include<iostream>using namespace std;// Linked List Implementationclass Node{public:char Data;Node* Next;Node(char data, Node* next){ Data = data; Next = next;}};// Function to create a linked list// from the given StringNode* CreateList(string s){Node* header = NULL;Node* temp = NULL;// Generates characters from the given stringfor (int i = 0; i < s.length(); i++){ char c = s[i]; Node* node = new Node(c, NULL); if (header == NULL) { header = node; temp = header; } else { temp->Next = node; temp = temp->Next; }}return header;}// Function to reverse the words// Assume str = "practice makes man perfect"// to understand proper understanding of the codeNode* Reverse(Node* header){if (header == NULL)return header;Node* wordStartPosition = NULL;Node* endOfSentence = NULL;Node* sentenceStartPosition = NULL;// Initialize wordStartPosition to header// ie. node 'p' first letter of the word 'practice'wordStartPosition = header;while (header != NULL && header->Data != ' '){ // Keep track the previous node. // This will become the // last node of the linked list endOfSentence = header; // Keep moving to the next node header = header->Next;} // After the above while loop, // endOfSentence points to // the last letter 'e'of word 'practice' // header points to the space(' ') // which is next to word 'practice' // If header is null then there is only // one word in the given sentance // so set header to the // first/wordStartPosition node and return.if (header == NULL){ header = wordStartPosition; return header;}do{ // Swapping the space ie. // convert 'practice<space>' to //'<space>practice' // store the node which is next to space(' ') // 'm' which is the first letter of the word 'make' Node* temp = header->Next; header->Next = wordStartPosition; wordStartPosition = header; header = temp; Node* prev = NULL; // Setting sentenceStartPosition to node 'm' //(first letter of the word 'make') sentenceStartPosition = header; while (header != NULL && header->Data != ' ') { prev = header; header = header->Next; } // When the next space is found, // change the pointer to point the previous space // ie. the word is being converted to // "m->a->k->e->s-> ->p->r->a->c->t->i->c->e" prev->Next = wordStartPosition; // Newly found space will point to //'m' first letter of the word 'make' wordStartPosition = sentenceStartPosition; if (header == NULL) break; // Repeat the loop until // the end of the linked list is reached}while (header != NULL);header = sentenceStartPosition;endOfSentence->Next = NULL;return header;}// Function to print the Linked Listvoid PrintList(Node* Header){Node* temp = Header;// Navigate till the end and print// the data in each nodewhile (temp != NULL){ cout << temp->Data; temp = temp->Next;}}// Driver codeint main(){string s = "practice makes a man perfect";// Convert given string to a linked list// with character as data in each nodeNode* header = CreateList(s);cout << "Before:\n";PrintList(header);header = Reverse(header);cout << "\nAfter:\n";PrintList(header);return 0;} |
Java
// Linked List Implementationclass Node { public Node(char data, Node next) { Data = data; Next = next; } public char Data; public Node Next;}class GFG { // Function to create a linked list // from the given String private static Node CreateLinkedList(String s) { Node header = null; Node temp = null; // Generates characters from the given string for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); Node node = new Node(c, null); if (header == null) { header = node; temp = header; } else { temp.Next = node; temp = temp.Next; } } return header; } // Function to reverse the words // Assume str = "practice makes man perfect" // to understand proper understanding of the code private static Node Reverse(Node header) { if (header == null) return header; Node wordStartPosition = null; Node endOfSentence = null; Node sentenceStartPosition = null; // Initialize wordStartPosition to header // ie. node 'p' first letter of the word 'practice' wordStartPosition = header; // Navigate the linked list until // a space(' ') is found or header is null //(this is for handing if there is // only one word in the given sentence) while (header != null && header.Data != ' ') { // Keep track the previous node. // This will become the // last node of the linked list endOfSentence = header; // Keep moving to the next node header = header.Next; } // After the above while loop, // endOfSentence points to // the last letter 'e'of word 'practice' // header points to the space(' ') // which is next to word 'practice' // If header is null then there is only // one word in the given sentence // so set header to the // first/wordStartPosition node and return. if (header == null) { header = wordStartPosition; return header; } do { // Swapping the space ie. // convert 'practice<space>' to //'<space>practice' // store the node which is next to space(' ') // 'm' which is the first letter of the word 'make' Node temp = header.Next; header.Next = wordStartPosition; wordStartPosition = header; header = temp; Node prev = null; // Setting sentenceStartPosition to node 'm' //(first letter of the word 'make') sentenceStartPosition = header; // Again Navigate the linked list until // a space(' ') is found or // header == null end of the linked list while (header != null && header.Data != ' ') { prev = header; header = header.Next; } // When the next space is found, // change the pointer to point the previous space // ie. the word is being converted to // "m->a->k->e->s-> ->p->r->a->c->t->i->c->e" prev.Next = wordStartPosition; // Newly found space will point to //'m' first letter of the word 'make' wordStartPosition = sentenceStartPosition; if (header == null) break; // Repeat the loop until // the end of the linked list is reached } while (header != null); header = sentenceStartPosition; // Set the last node's next to null // ie. ->m->a->k->e->s-> ->p->r->a->->c->t->i->c->e->null endOfSentence.Next = null; return header; } // Function to print the Linked List private static void PrintList(Node Header) { Node temp = Header; // Navigate till the end and print the data in each node while (temp != null) { System.out.print(temp.Data); temp = temp.Next; } } // Driver code public static void main(String[] args) { String s = "practice makes a man perfect"; // Convert given string to a linked list // with character as data in each node Node header = CreateLinkedList(s); System.out.println("Before:"); PrintList(header); header = Reverse(header); System.out.println("\nAfter:"); PrintList(header); }} |
Python3
# Python equivalent of the above codeclass Node: def __init__(self, data, next=None): self.data = data self.next = nextclass GFG: # Function to create a linked list # from the given String def CreateLinkedList(s): header = None temp = None # Generates characters from the given string for i in range(len(s)): char = s[i] node = Node(char, None) if header is None: header = node temp = header else: temp.next = node temp = temp.next return header # Function to reverse the words # Assume str = "practice makes man perfect" # to understand proper understanding of the code def Reverse(header): if header is None: return header wordStartPosition = None endOfSentence = None sentenceStartPosition = None # Initialize wordStartPosition to header # ie. node 'p' first letter of the word 'practice' wordStartPosition = header # Navigate the linked list until # a space(' ') is found or header is null #(this is for handing if there is # only one word in the given sentence) while header is not None and header.data != ' ': # Keep track the previous node. # This will become the # last node of the linked list endOfSentence = header # Keep moving to the next node header = header.next # After the above while loop, # endOfSentence points to # the last letter 'e'of word 'practice' # header points to the space(' ') # which is next to word 'practice' # If header is null then there is only # one word in the given sentence # so set header to the # first/wordStartPosition node and return. if header is None: header = wordStartPosition return header while header is not None and header.data == ' ': temp = header.next header.next = wordStartPosition wordStartPosition = header header = temp prev = None sentenceStartPosition = header while header is not None and header.data != ' ': prev = header header = header.next prev.next = wordStartPosition wordStartPosition = sentenceStartPosition if header is None: break header = sentenceStartPosition endOfSentence.next = None return header # Function to print the Linked List def PrintList(Header): temp = Header # Navigate till the end and print the data in each node while temp is not None: print(temp.data, end="") temp = temp.next # Driver code def main(args): s = "practice makes a man perfect" # Convert given string to a linked list # with character as data in each node header = GFG.CreateLinkedList(s) print("Before:") GFG.PrintList(header) header = GFG.Reverse(header) print("\nAfter:") GFG.PrintList(header)if __name__ == "__main__": GFG.main(None) |
Javascript
class Node { constructor(data, next) { this.Data = data; this.Next = next; }} // Function to create a linked list// from the given Stringfunction createLinkedList(s) { let header = null; let temp = null; // Generates characters from the given string for (let i = 0; i < s.length; i++) { const c = s.charAt(i); const node = new Node(c, null); if (header === null) { header = node; temp = header; } else { temp.Next = node; temp = temp.Next; } } return header;} // Function to reverse the words// Assume str = "practice makes man perfect"// to understand proper understanding of the codefunction reverse(header) { if (header === null) return header; let wordStartPosition = null; let endOfSentence = null; let sentenceStartPosition = null; // Initialize wordStartPosition to header // ie. node 'p' first letter of the word 'practice' wordStartPosition = header; // Navigate the linked list until // a space(' ') is found or header is null //(this is for handing if there is // only one word in the given sentence) while (header !== null && header.Data !== " ") { // Keep track the previous node. // This will become the // last node of the linked list endOfSentence = header; // Keep moving to the next node header = header.Next; } // After the above while loop, // endOfSentence points to // the last letter 'e'of word 'practice' // header points to the space(' ') // which is next to word 'practice' // If header is null then there is only // one word in the given sentence // so set header to the // first/wordStartPosition node and return if (header === null) { header = wordStartPosition; return header; } do { // Swapping the space ie. // convert 'practice<space>' to //'<space>practice' // store the node which is next to space(' ') // 'm' which is the first letter of the word 'make' const temp = header.Next; header.Next = wordStartPosition; wordStartPosition = header; header = temp; let prev = null; // Setting sentenceStartPosition to node 'm' //(first letter of the word 'make') sentenceStartPosition = header; // Again Navigate the linked list until // a space(' ') is found or // header == null end of the linked list while (header !== null && header.Data !== " ") { prev = header; header = header.Next; } // When the next space is found, // change the pointer to point the previous space // ie. the word is being converted to // "m->a->k->e->s-> ->p->r->a->c->t->i->c->e" prev.Next = wordStartPosition; // Newly found space will point to //'m' first letter of the word 'make' wordStartPosition = sentenceStartPosition; if (header === null) break; // Repeat the loop until // the end of the linked list is reached } while (header !== null); header = sentenceStartPosition; // Set the last node's next to null// ie. ->m->a->k->e->s-> ->p->r->a->->c->t->i->c->e->null endOfSentence.Next = null; return header;} // Function to print the Linked Listfunction printList(header) { let temp = header; let result = ""; // Navigate till the end and print the data in each node while (temp !== null) { result += temp.Data; temp = temp.Next; } return result;}const s = "practice makes a man perfect";// Convert given string to a linked list// with character as data in each nodelet header = createLinkedList(s);console.log("Before:");console.log(printList(header));header = reverse(header);console.log("After:");console.log(printList(header)); |
C#
using System;// Linked List Implementationpublic class Node { public Node(char data, Node next) { Data = data; Next = next; } public char Data; public Node Next;}class GFG { // Function to create a linked list // from the given String private static Node CreateList(String s) { Node header = null; Node temp = null; // Generates characters from the given string for (int i = 0; i < s.Length; i++) { char c = s[i]; Node node = new Node(c, null); if (header == null) { header = node; temp = header; } else { temp.Next = node; temp = temp.Next; } } return header; } // Function to reverse the words // Assume str = "practice makes man perfect" // to understand proper understanding of the code private static Node Reverse(Node header) { if (header == null) return header; Node wordStartPosition = null; Node endOfSentence = null; Node sentenceStartPosition = null; // Initialize wordStartPosition to header // ie. node 'p' first letter of the word 'practice' wordStartPosition = header; // Navigate the linked list until // a space(' ') is found or header is null //(this is for handing if there is // only one word in the given sentence) while (header != null && header.Data != ' ') { // Keep track the previous node. // This will become the // last node of the linked list endOfSentence = header; // Keep moving to the next node header = header.Next; } // After the above while loop, // endOfSentence points to // the last letter 'e'of word 'practice' // header points to the space(' ') // which is next to word 'practice' // If header is null then there is only // one word in the given sentance // so set header to the // first/wordStartPosition node and return. if (header == null) { header = wordStartPosition; return header; } do { // Swapping the space ie. // convert 'practice<space>' to //'<space>practice' // store the node which is next to space(' ') // 'm' which is the first letter of the word 'make' Node temp = header.Next; header.Next = wordStartPosition; wordStartPosition = header; header = temp; Node prev = null; // Setting sentenceStartPosition to node 'm' //(first letter of the word 'make') sentenceStartPosition = header; // Again Navigate the linked list until // a space(' ') is found or // header == null end of the linked list while (header != null && header.Data != ' ') { prev = header; header = header.Next; } // When the next space is found, // change the pointer to point the previous space // ie. the word is being converted to // "m->a->k->e->s-> ->p->r->a->c->t->i->c->e" prev.Next = wordStartPosition; // Newly found space will point to //'m' first letter of the word 'make' wordStartPosition = sentenceStartPosition; if (header == null) break; // Repeat the loop until // the end of the linked list is reached } while (header != null); header = sentenceStartPosition; // Set the last node's next to null // ie. ->m->a->k->e->s-> ->p->r->a->->c->t->i->c->e->null endOfSentence.Next = null; return header; } // Function to print the Linked List private static void PrintList(Node Header) { Node temp = Header; // Navigate till the end and print // the data in each node while (temp != null) { Console.Write(temp.Data); temp = temp.Next; } } // Driver code public static void Main(String[] args) { String s = "practice makes a man perfect"; // Convert given string to a linked list // with character as data in each node Node header = CreateList(s); Console.WriteLine("Before:"); PrintList(header); header = Reverse(header); Console.WriteLine("\nAfter:"); PrintList(header); }}// This code is contributed by Rajput-Ji |
Output:
Before: practice makes a man perfect After: perfect man a makes practice
Time Complexity: O(n)
Auxiliary Space: O(n)
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!
