வரிசைப்படுத்தப்பட்ட இரண்டு பட்டியல்கள் லீட்கோடை இணைக்கவும்  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ஆப்பிள் ப்ளூம்பெர்க் மூலதன ஒன்று பேஸ்புக் கூகிள் ஐபிஎம் மைக்ரோசாப்ட் ஆரக்கிள்
குறியீட்டு பேட்டி நேர்காணல் தயாரிப்பு லீட்கோட் LeetCodeSolutions இணைக்கப்பட்ட பட்டியல் வரிசையாக்க

லீட்கோடில் இரண்டு வரிசைப்படுத்தப்பட்ட பட்டியல்களின் சிக்கல் என்ன?  

அமேசான், ஆரக்கிள், மைக்ரோசாப்ட் போன்ற நிறுவனங்களில் இது பல முறை கேட்கப்பட்ட சுவாரஸ்யமான கேள்வி. இந்த சிக்கலில் (இரண்டு வரிசைப்படுத்தப்பட்ட பட்டியல்களை லீட்கோடை ஒன்றிணைத்தல்), நாங்கள் இரண்டு இணைக்கப்பட்ட பட்டியல்களை வழங்கியுள்ளோம். இருவரும் இணைக்கப்பட்ட பட்டியல்கள் அதிகரிக்கும் வரிசையில் உள்ளன. செல்ல இணைக்கப்பட்ட புதிய பட்டியல் புதிய வரிசையில் இணைக்கப்பட்ட பட்டியல் அதிகரிக்கும் வரிசையில் உள்ளது.

உதாரணமாக  

உள்ளீடு

2-> 4-> 6

1-> 3-> 5-> 7

வெளியீடு

1->2->3->4->5->6->7

விளக்கம்

வரிசைப்படுத்தப்பட்ட இரண்டு பட்டியல்கள் லீட்கோடை இணைக்கவும்முள்

2-> 4-> 6 மற்றும் 1-> 3-> 5-> 7 ஆகிய இரண்டு இணைக்கப்பட்ட பட்டியல் எங்களுக்கு வழங்கப்பட்டுள்ளது, அவற்றை நாம் ஒன்றிணைத்து அதிகரிக்கும் வரிசையில் வரிசைப்படுத்தும்போது அவை 1-> 2-> 3-> 4-> 5 -> 6-> 7.

இரண்டு வரிசைப்படுத்தப்பட்ட பட்டியல்கள் லீட்கோடை ஒன்றிணைப்பதற்கான அணுகுமுறை  

நாங்கள் மிகவும் எளிமையான அணுகுமுறையைப் பயன்படுத்துவோம். முடிவு இணைக்கப்பட்ட பட்டியல் காலியாக இருக்கும்போது இங்கே நாம் போலி முனையைப் பயன்படுத்தலாம். முடிவு இணைக்கப்பட்ட பட்டியலின் வால் சுட்டிக்காட்டி எப்போதும் முடிவு இணைக்கப்பட்ட பட்டியலில் கடைசி முனைக்கு சுட்டிக்காட்டுகிறது.

  • முதல் இணைக்கப்பட்ட பட்டியலிலிருந்து அல்லது இரண்டாவது, இணைக்கப்பட்ட பட்டியலிலிருந்து முனைகளைச் சேர்ப்போம், இதன் விளைவாக இணைக்கப்பட்ட பட்டியல் அதிகரிக்கும் வரிசையில் உள்ளது.
  • இணைக்கப்பட்ட பட்டியல்களில் ஒன்றின் அனைத்து கூறுகளும் முடிவு இணைக்கப்பட்ட பட்டியலில் சேர்க்கப்படும்போது, ​​மற்ற இணைக்கப்பட்ட பட்டியலை முடிவு இணைக்கப்பட்ட பட்டியலுடன் இணைப்போம்.
  • இப்போது நாம் போலி முனையின் அடுத்ததைத் தருகிறோம்.
மேலும் காண்க
இரண்டு லீட்கோட் தீர்வின் சக்தி

இரண்டு வரிசைப்படுத்தப்பட்ட பட்டியல்கள் லீட்கோடை ஒன்றிணைப்பதற்கான நடைமுறை  

சி ++ குறியீடு 

/* C++ program to merge two sorted linked lists */
#include <bits/stdc++.h> 
using namespace std; 

/* Link list node */
class Node 
{ 
  public: 
  int data; 
  Node* next; 
}; 

/* pull off the front node of 
the source and put it in dest */
void MoveNode(Node** destRef, Node** sourceRef); 


Node* SortedMerge(Node* a, Node* b) 
{ 
  /* a dummy first node to hang the result on */
  Node dummy; 

  /* tail points to the last result node */
  Node* tail = &dummy; 

  /* so tail->next is the place to 
  add new nodes to the result. */
  dummy.next = NULL; 
  while (1) 
  { 
    if (a == NULL) 
    { 
      /* if either list runs out, use the 
      other list */
      tail->next = b; 
      break; 
    } 
    else if (b == NULL) 
    { 
      tail->next = a; 
      break; 
    } 
    if (a->data <= b->data) 
      MoveNode(&(tail->next), &a); 
    else
      MoveNode(&(tail->next), &b); 

    tail = tail->next; 
  } 
  return(dummy.next); 
} 

/* UTILITY FUNCTIONS */
/* MoveNode() function takes the 
node from the front of the source, 
and move it to the front of the dest. 
It is an error to call this with the 
source list empty. 

Before calling MoveNode(): 
source == {1, 2, 3} 
dest == {1, 2, 3} 

Affter calling MoveNode(): 
source == {2, 3} 
dest == {1, 1, 2, 3} */
void MoveNode(Node** destRef, Node** sourceRef) 
{ 
  /* the front source node */
  Node* newNode = *sourceRef; 
  assert(newNode != NULL); 

  /* Advance the source pointer */
  *sourceRef = newNode->next; 

  /* Link the old dest off the new node */
  newNode->next = *destRef; 

  /* Move dest to point to the new node */
  *destRef = newNode; 
} 

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 nodes in a given 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* res = NULL; 
  Node* a = NULL; 
  Node* b = NULL; 

  /* Let us create two sorted linked lists 
  to test the functions 
  Created lists, a: 5->10->15, b: 2->3->20 */
  push(&a, 15); 
  push(&a, 10); 
  push(&a, 5); 

  push(&b, 20); 
  push(&b, 3); 
  push(&b, 2); 

  /* Remove duplicates from linked list */
  res = SortedMerge(a, b); 

  cout << "Merged Linked List is: \n"; 
  printList(res); 

  return 0; 
}
Merged Linked List is: 
2 3 5 10 15 20

ஜாவா குறியீடு

/* Java program to merge two 
sorted linked lists */
import java.util.*; 

/* Link list node */
class Node 
{ 
  int data; 
  Node next; 
  Node(int d) {data = d; 
        next = null;} 
} 
  
class MergeLists 
{ 
Node head; 

/* Method to insert a node at 
the end of the linked list */
public void addToTheLast(Node node) 
{ 
  if (head == null) 
  { 
    head = node; 
  } 
  else
  { 
    Node temp = head; 
    while (temp.next != null) 
      temp = temp.next; 
    temp.next = node; 
  } 
} 

/* Method to print linked list */
void printList() 
{ 
  Node temp = head; 
  while (temp != null) 
  { 
    System.out.print(temp.data + " "); 
    temp = temp.next; 
  } 
  System.out.println(); 
} 


// Driver Code 
public static void main(String args[]) 
{ 
  /* Let us create two sorted linked 
  lists to test the methods 
  Created lists: 
    llist1: 5->10->15, 
    llist2: 2->3->20 
  */
  MergeLists llist1 = new MergeLists(); 
  MergeLists llist2 = new MergeLists(); 
  
  // Node head1 = new Node(5); 
  llist1.addToTheLast(new Node(5)); 
  llist1.addToTheLast(new Node(10)); 
  llist1.addToTheLast(new Node(15)); 
  
  // Node head2 = new Node(2); 
  llist2.addToTheLast(new Node(2)); 
  llist2.addToTheLast(new Node(3)); 
  llist2.addToTheLast(new Node(20)); 
  
  
  llist1.head = new Gfg().sortedMerge(llist1.head, 
                    llist2.head); 
  llist1.printList();	 
  
} 
} 

class check
{ 

Node sortedMerge(Node headA, Node headB) 
{ 
  
  /* a dummy first node to 
  hang the result on */
  Node dummyNode = new Node(0); 
  
  /* tail points to the 
  last result node */
  Node tail = dummyNode; 
  while(true) 
  { 
    
    /* if either list runs out, 
    use the other list */
    if(headA == null) 
    { 
      tail.next = headB; 
      break; 
    } 
    if(headB == null) 
    { 
      tail.next = headA; 
      break; 
    } 
    
    /* Compare the data of the two 
    lists whichever lists' data is 
    smaller, append it into tail and 
    advance the head to the next Node 
    */
    if(headA.data <= headB.data) 
    { 
      tail.next = headA; 
      headA = headA.next; 
    } 
    else
    { 
      tail.next = headB; 
      headB = headB.next; 
    } 
    
    /* Advance the tail */
    tail = tail.next; 
  } 
  return dummyNode.next; 
} 
}
Merged Linked List is: 
2 3 5 10 15 20

நேர சிக்கலானது  

O (n + m) n மற்றும் m ஆகியவை முதல் மற்றும் இரண்டாவது இணைக்கப்பட்ட பட்டியலின் நீளம்.

மேலும் காண்க
ஒவ்வொரு முனையிலும் அடுத்த வலது சுட்டிகள் பிரபலப்படுத்துகின்றன

விண்வெளி சிக்கலானது  

ஓ (1) நாங்கள் போலி முனையைப் பயன்படுத்துகிறோம்.

குறிப்புகள்