दुवा साधलेली यादी उलट करा  


अडचण पातळी सोपे
वारंवार विचारले एकत्रित अडोब ऍमेझॉन मेकमायट्रिप मायक्रोसॉफ्ट Qualcomm सॅमसंग सॅप एसएपी लॅब Snapdeal Zoho
दुवा साधलेली यादी

समस्या विधान  

समस्या “रिव्हर्स अ जोडलेली यादी ” असे म्हटले आहे की आम्हाला लिंक केलेल्या यादीचा प्रमुख देण्यात आला आहे. आम्हाला त्यामधील दुवे बदलून दुवा साधलेली यादी उलट करावी लागेल आणि उलट दुवा साधलेल्या सूचीचे प्रमुख परत करावे लागेल.

उदाहरण  

10->20->30->40->NULL
NULL<-10<-20<-30<-40

स्पष्टीकरण

आम्ही त्यांच्यामधील दुवे बदलून दुवा साधलेली यादी उलट केली आहे. तर रिव्हर्स ऑपरेशन केल्यानंतर नवीन जोडलेली यादी 40-> 30-> 20-> 10-> NULL बनते.

उलट लिंक केलेल्या यादीसाठी पध्दत  

Iterative दृष्टीकोन

    1. प्रमुख म्हणून वर्तमान पॉईंटर प्रारंभ करा.
    2. मागील आणि पुढील पॉईंटर एनयूएल म्हणून प्रारंभ करा.
    3. सध्याच्या पॉईंटपर्यंत एनओएलएल पर्यंत लूप चालवा.
      1. पुढील पॉईंटर च्या पुढे करंट द्या.
      2. आताच्या पॉईंटरला करंटच्या पुढच्या पॉईंटरवर नेम द्या.
      3. चालू पुढे मागील चालू द्या.
    4. मागीलला डोके द्या.

दुवा साधलेली यादी उलट करापिन

पिन

सी ++ कोड

#include <iostream>
using namespace std;
struct Node {
  int data;
  struct Node* next;
  Node(int data)
  {
    this->data = data;
    next = NULL;
  }
};
struct LinkedList {
  Node* head;
  LinkedList()
  {
    head = NULL;
  }
  void reverse()
  {
    Node* current = head;
    Node *prev = NULL, *next = NULL;
    while (current != NULL) {
      next = current->next;
      current->next = prev;
      prev = current;
      current = next;
    }
    head = prev;
  }
  void print()
  {
    struct Node* temp = head;
    while (temp != NULL) {
      cout << temp->data << " ";
      temp = temp->next;
    }
  }
  void push(int data)
  {
    Node* temp = new Node(data);
    temp->next = head;
    head = temp;
  }
};
int main()
{
  LinkedList ll;
  ll.push(40);
  ll.push(30);
  ll.push(20);
  ll.push(10);
  cout << "old linked list\n";
  ll.print();
  ll.reverse();
  cout << "\nnew Linked list \n";
  ll.print();
  return 0;
}
old linked list: 
10 20 30 40

new Linked list: 
40 30 20 10

जावा कोड 

class LinkedList { 
  static Node head; 
  static class Node { 
    int data; 
    Node next; 
    Node(int d) 
    { 
      data = d; 
      next = null; 
    } 
  } 
  Node reverse(Node node) 
  { 
    Node prev = null; 
    Node current = node; 
    Node next = null; 
    while (current != null) { 
      next = current.next; 
      current.next = prev; 
      prev = current; 
      current = next; 
    } 
    node = prev; 
    return node; 
  } 
  void printList(Node node) 
  { 
    while (node != null) { 
      System.out.print(node.data + " "); 
      node = node.next; 
    } 
  } 
  public static void main(String[] args) 
  { 
    LinkedList list = new LinkedList(); 
    list.head = new Node(10); 
    list.head.next = new Node(20); 
    list.head.next.next = new Node(30); 
    list.head.next.next.next = new Node(40); 
    System.out.println("old Linked list"); 
    list.printList(head); 
    head = list.reverse(head); 
    System.out.println(""); 
    System.out.println("new linked list "); 
    list.printList(head); 
  } 
} 
old linked list: 
10 20 30 40

new Linked list: 
40 30 20 10

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) कारण आम्ही फक्त एकदाच लिंक केलेल्या यादीचा मागोवा घेत आहोत.

हे सुद्धा पहा
दोन दुवा साधलेल्या सूच्यांचा छेदनबिंदू मिळविण्यासाठी कार्य लिहा
स्पेस कॉम्प्लेक्सिटी

ओ (1) कारण आम्ही केवळ तात्पुरते व्हेरिएबल्स संचयित करण्यासाठी जागा वापरत आहोत.

रिकर्सिव्ह दृष्टीकोन 

  • आम्ही दुवा साधलेल्या सूचीतून ट्रॅव्हर्स करून शेवटचे नोड हेड नोड म्हणून नियुक्त करतो.
  • आणि लिंक केलेल्या यादीची शेवटची परतलेली शेपटी त्याच्या मागील नोडसह जोडा. या चरणानंतर पुनरावृत्ती होते.

सी ++ कोड 

#include <iostream> 
using namespace std; 
struct Node { 
  int data; 
  struct Node* next; 
  Node(int data) 
  { 
    this->data = data; 
    next = NULL; 
  } 
}; 
struct LinkedList { 
  Node* head; 
  LinkedList() 
  { 
    head = NULL; 
  } 
  Node* reverse(Node* node) 
  { 
    if (node == NULL) 
      return NULL; 
    if (node->next == NULL) { 
      head = node; 
      return node; 
    } 
    Node* node1 = reverse(node->next); 
    node1->next = node; 
    node->next = NULL; 
    return node; 
  } 
  /* Function to print linked list */
  void print() 
  { 
    struct Node* temp = head; 
    while (temp != NULL) { 
      cout << temp->data << " "; 
      temp = temp->next; 
    } 
  } 
  void push(int data) 
  { 
    Node* temp = new Node(data); 
    temp->next = head; 
    head = temp; 
  } 
}; 
int main() 
{ 
  LinkedList ll; 
  ll.push(40); 
  ll.push(30); 
  ll.push(20); 
  ll.push(10); 
  cout << "old linked list\n"; 
  ll.print(); 
  ll.reverse(ll.head); 
  cout << "\n new Linked list \n"; 
  ll.print(); 
  return 0; 
} 
old linked list: 
10 20 30 40

new Linked list: 
40 30 20 10

दुवा साधलेल्या सूचीच्या उलट करण्यासाठी जावा कोड

import java.io.BufferedWriter; 
import java.io.IOException; 
import java.io.OutputStreamWriter; 
import java.util.Scanner; 
class ReverseLinkedListRecursive { 
    static class Node { 
    public int data; 
    public Node next; 
    public Node(int nodeData) { 
      this.data = nodeData; 
      this.next = null; 
    } 
  } 
  static class LinkedList { 
    public Node head; 
    public LinkedList() { 
      this.head = null; 
    } 
    public void insertNode(int nodeData) { 
      Node node = new Node(nodeData); 
      if (this.head != null) { 
        node.next = head; 
      } 
      this.head = node; 
    } 
  } 
  public static void printSinglyLinkedList(Node node, 
            String sep) throws IOException { 
    while (node != null) { 
      System.out.print(String.valueOf(node.data) + sep); 
      node = node.next; 
    } 
  } 
  static Node reverse(Node head) { 
    if(head == null) { 
      return head; 
    } 
    if(head.next == null) { 
      return head; 
    } 
    Node newHeadNode = reverse(head.next); 
    head.next.next = head; 
    head.next = null; 
    return newHeadNode; 
  } 
  private static final Scanner scanner = new Scanner(System.in); 
  public static void main(String[] args) throws IOException { 
      LinkedList llist = new LinkedList(); 
    
      llist.insertNode(40); 
      llist.insertNode(30); 
      llist.insertNode(20); 
      llist.insertNode(10); 
      
      System.out.println("old linked list:"); 
      printSinglyLinkedList(llist.head, " "); 
      
      System.out.println(); 
      System.out.println("new Linked list:"); 
      Node llist1 = reverse(llist.head); 
      printSinglyLinkedList(llist1, " "); 
    scanner.close(); 
  } 
} 
old linked list: 
10 20 30 40

new Linked list: 
40 30 20 10

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) कारण आम्ही फक्त एकदाच लिंक केलेल्या यादीचा मागोवा घेत आहोत.

हे सुद्धा पहा
दिलेल्या बायनरी झाडामध्ये अनुलंब बेरीज
स्पेस कॉम्प्लेक्सिटी

O (n) कारण आम्ही कंपाईलर स्टॅकवर तात्पुरते व्हेरिएबल्स संचयित करण्यासाठी जागा वापरत आहोत. हे तात्पुरते बदल लिंक्ड सूचीतील नोड्सच्या संख्येवर अवलंबून असतात.

टेल रिकर्सिव्ह दृष्टीकोन 

हा दृष्टिकोन एक प्रकारचा पुनरावृत्ती आहे ज्यास टेल रिकर्सन देखील म्हणतात. शेपटीच्या पुनरावृत्तीमध्ये, आम्ही कॉल सुरू केलेल्या फंक्शनकडे परत जाण्याची आवश्यकता नाही. आम्ही मागील कॉलची रिझल्ट व्हॅल्यू नवीन फंक्शन कॉलला पॅरामीटर म्हणून पास करतो. हे कंपाईलर स्तरावर देखील उपयुक्त आहे कारण मागील कॉलचे मूल्य संचयित करण्यासाठी आम्हाला सिस्टम स्टॅकची देखभाल करण्याची आवश्यकता नाही. हे स्टॅक ओव्हरफ्लोपासून प्रतिबंधित करण्यास देखील उपयुक्त आहे.

सी ++ कोड 

#include <bits/stdc++.h> 
using namespace std; 
struct Node { 
  int data; 
  struct Node* next; 
}; 
void reverseUtil(Node* curr, Node* prev, Node** head); 
void reverse(Node** head) 
{ 
  if (!head) 
    return; 
  reverseUtil(*head, NULL, head); 
} 
void reverseUtil(Node* curr, Node* prev, Node** head) 
{ 
  if (!curr->next) { 
    *head = curr; 
    curr->next = prev; 
    return; 
  } 
  Node* next = curr->next; 
  curr->next = prev; 
  reverseUtil(next, curr, head); 
} 
Node* newNode(int key) 
{ 
  Node* temp = new Node; 
  temp->data = key; 
  temp->next = NULL; 
  return temp; 
} 
void printlist(Node* head) 
{ 
  while (head != NULL) { 
    cout << head->data << " "; 
    head = head->next; 
  } 
  cout << endl; 
} 
int main() 
{ 
  Node* head1 = newNode(1); 
  head1->next = newNode(2); 
  head1->next->next = newNode(3); 
  head1->next->next->next = newNode(4); 
  head1->next->next->next->next = newNode(5); 
  head1->next->next->next->next->next = newNode(6); 
  head1->next->next->next->next->next->next = newNode(7); 
  head1->next->next->next->next->next->next->next = newNode(8); 
  cout << "old linked list\n"; 
  printlist(head1); 
  reverse(&head1); 
  cout << "\nnew linked list\n"; 
  printlist(head1); 
  return 0; 
} 
old linked list
1 2 3 4 5 6 7 8

new linked list
8 7 6 5 4 3 2 1

जावा कोड 

class LinkedList { 
  static Node head; 
  static class Node { 
    int data; 
    Node next; 
    Node(int d) 
    { 
      data = d; 
      next = null; 
    } 
  } 
  Node reverseUtil(Node curr, Node prev) 
  { 
    if (curr.next == null) { 
      head = curr; 
      curr.next = prev; 
      return head; 
    } 
    Node next1 = curr.next; 
    curr.next = prev; 
    reverseUtil(next1, curr); 
    return head; 
  } 
  void printList(Node node) 
  { 
    while (node != null) { 
      System.out.print(node.data + " "); 
      node = node.next; 
    } 
  } 
  public static void main(String[] args) 
  { 
    LinkedList list = new LinkedList(); 
    list.head = new Node(1); 
    list.head.next = new Node(2); 
    list.head.next.next = new Node(3); 
    list.head.next.next.next = new Node(4); 
    list.head.next.next.next.next = new Node(5); 
    list.head.next.next.next.next.next = new Node(6); 
    list.head.next.next.next.next.next.next = new Node(7); 
    list.head.next.next.next.next.next.next.next = new Node(8); 
    System.out.println("Old Linked list "); 
    list.printList(head); 
    Node res = list.reverseUtil(head, null); 
    System.out.println(""); 
    System.out.println(""); 
    System.out.println("new linked list "); 
    list.printList(res); 
  } 
}
old linked list 
1 2 3 4 5 6 7 8
new linked list 
8 7 6 5 4 3 2 1

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) कारण आम्ही फक्त एकदाच लिंक केलेल्या यादीचा मागोवा घेत आहोत.

हे सुद्धा पहा
युनियन आणि दोन दुवा साधलेल्या सूचीचे छेदनबिंदू
स्पेस कॉम्प्लेक्सिटी

O (n) कारण आम्ही केवळ कंपाईलर स्टॅकवर तात्पुरते व्हेरिएबल्स संचयित करण्यासाठी जागा वापरत आहोत. हे तात्पुरते बदल लिंक्ड सूचीतील नोड्सच्या संख्येवर अवलंबून असतात.

संदर्भ