ترتيب ڏنل لسٽ II مان نقل نقل ڪيو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon
ڳن -يل فهرست

مسئلو ”ترتيب وار فهرست II مان نقل نقل ڪ Removeي ٿو“ ٻڌائي ٿو ته توهان کي هڪ ڳن listيل فهرست ڏني وئي آهي جيڪا شايد نقل واري عنصر نه هجي يا نه. جيڪڏهن لسٽ ٻٻرندڙ عناصر آهن ته پوءِ انهن فهرستن مان سڀئي خارج ڪريو. هيٺين آپريشن ڪرڻ کان پوءِ ، ڳن listيل فهرست آخر ۾ پرنٽ ڪريو.

مثال

ترتيب ڏنل لسٽ II مان نقل نقل ڪيو

Elements of linked list: 1 2 2 2 3 5 7 7
List after removing all the elements: 1 3 5

وضاحت

نمبر 2 لسٽ ۾ 3 مثال آھن. ان ڪري اسان هن جي سڀني صورتن کي ختم ڪيو. نمبر 7 سان ساڳيو ئي ٿيو ، تنهنڪري 2 ۽ 7 جا مثال ختم ڪرڻ بعد اسان 3 عنصر سان ڇڏي ويا آهيون جيڪي 1 3 5 آهن.

چرچو

مسئلو ”ترتيب وار فهرست II مان نقل خارج ڪريو“ ، جيئن statedاڻايل ئي فهرستن مان اسان کي اهي سڀ انگ اکر ختم ڪرڻ لاءِ چوندو آهي جيڪي نقل ۾ موجود آهن. هڪ ڀيرو بحث هيٺ مسئلو هو. پر موجوده مسئلو ۾ ٿورو فرق آهي. اڳوڻو مسئلو اسان کان پڇيو فقط نقلَ ختم ڪريو. اھو آھي ته اسان نقل نقل حذف ڪيا پر ان عنصر جي ھڪڙي ڪاپي جن جا نقل نقل موجود ھيا. هتي اسان کي هر هڪ ڪاپي ۽ اصل عنصر پڻ ڪ toڻو پوندو جنهن جي لسٽ ۾ ان جون نقلون موجود آهن.

تنهن ڪري ، اسان هاڻي مسئلو سان واقف آهيون. اسان مسئلي کي حل ڪرڻ جا طريقا سوچي سگھون ٿا. اسان پهريان ئي knowاڻون ٿا ته فهرست ترتيب ڏنل آهي. تنهن ڪري اسان انهي حقيقت کي استعمال ڪري سگهون ٿا. جيڪڏهن فهرست ترتيب ڏني وئي ، اسان کي پڪ آهي ته جيڪڏهن ڪو به نقل موجود آهي. اهي هميشه هڪ گروپ ۾ شامل ٿيندا آهن. تنهن ڪري ، اسان کي نقل جي ويجهڙائي وارن عناصر کي جانچڻ جي ضرورت آهي. جيڪڏھن اسان ھڪڙي جوڙي ۾ اچو. پهرين ، اسان لسٽ کي ڇڪيو وڃي ٿو جيستائين اسان غيرفطني عنصر کي نه ڳولي يا فهرست ختم نه ٿئي. انهي نقطي تي ، اسين پويون نوڊ هن نئين غير نقل واري عنصر ڏانهن اشارو ڪريون ٿا. وري ٻيهر دوپري عنصر جي ڳولهڻ شروع ڪيو هن غير نقل واري عنصر کان.

اصطلاح “غير نقل” جي ذريعي ، اسان جو مطلب اهو ناهي ته موجوده عنصر لسٽ ۾ نقل نه آهي. ان جو اهو ئي مطلب آهي ته موجوده نوڊس هن عنصر سان برابر ناهي. غور ڪريو ، اسان وٽ لسٽ ۾ 1 ، 2 ، 2 ، 2 ، 3 ، 3. اسان 1 کان 3. کي اشارو ڪيون ٿا ، 3 کي به ختم ڪيو ويندو. پر ڪجهه وقت تي ، جڏهن اسان ويجهي عناصر کي جانچ ڪري رهيا هئاسين ۽ پهرين 2 2 جوڙي جي پار آياسين. اسان اهو چئون ٿا ته 3 هڪ بلڪل نقل آهي ڇاڪاڻ ته اهو 2 نه آهي.

تنهن ڪري ، اهو خلاصو ڪرڻ لاءِ. اسان س theي فهرست مان گذري چڪا آهيون. ۽ چڪاس جاري رکندا ته ايندڙ عنصر موجوده عنصر وانگر ئي آهي يا نه. جيڪڏهن اهو ٿئي ٿو ته ايستائين عناصر کي هٽائڻ تي رکو تيستائين توهان هڪ نقلي عنصر نه ڏسندا.

ڪوڊ

ترتيب وار فهرست II مان نقل نقل ڪ Removeڻ لاءِ C ++ ڪوڊ

#include <bits/stdc++.h>
using namespace std;

struct ListNode{
  int data;
  ListNode *next;
};

ListNode* create(int data){
  ListNode* tmp = new ListNode();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

ListNode* deleteDuplicates(ListNode* head) {
    if(head==NULL || head->next==NULL)
        return head;
    ListNode* prev = create(-1);
    ListNode* dummy = prev;
    ListNode* cur = head;
    prev->next = cur;
    while(cur && cur->next) {
        if(cur->data == cur->next->data) {
            while(cur->next && cur->data==cur->next->data) {
                ListNode* tmp = cur;
                cur = cur->next;
                free(tmp);
            }
            prev->next = cur->next;
            free(cur);
            cur = prev->next;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
    return dummy->next;
}

void printLinkedList(ListNode *headA){
  while(headA != NULL){
    cout<<headA->data<<" ";
    headA = headA->next;
  }
}

int main(){
  ListNode *headA = create(1);
  headA->next = create(2);
  headA->next->next = create(2);
  headA->next->next->next = create(2);
  headA->next->next->next->next = create(3);
  headA->next->next->next->next->next = create(5);
  headA->next->next->next->next->next->next = create(7);
  headA->next->next->next->next->next->next->next = create(7);

  headA = deleteDuplicates(headA);
  printLinkedList(headA);
}
1 3 5

جاوا ڪوڊ ترتيب ڏنل فهرست II مان نقل خارج ڪرڻ لاءِ

import java.util.*;
class ListNode{
  int data;
  ListNode next;
}

class Main{

    static ListNode create(int data){
        ListNode tmp = new ListNode();
        tmp.data = data;
        tmp.next = null;
        return tmp;
    }

  static ListNode deleteDuplicates(ListNode head) {
      if(head==null || head.next==null)
          return head;
      ListNode prev = create(-1);
      ListNode dummy = prev;
      ListNode cur = head;
      prev.next = cur;
      while(cur != null && cur.next != null) {
          if(cur.data == cur.next.data) {
              while(cur.next != null && cur.data==cur.next.data) {
                  ListNode tmp = cur;
                  cur = cur.next;
              }
              prev.next = cur.next;
              cur = prev.next;
          } else {
              prev = cur;
              cur = cur.next;
          }
      }
      return dummy.next;
  }

  static void printLinkedList(ListNode headA){
    while(headA != null){
      System.out.print(headA.data+" ");
      headA = headA.next;
    }
  }

    public static void main(String[] args){
    	ListNode headA = create(1);
    headA.next = create(2);
    headA.next.next = create(2);
    headA.next.next.next = create(2);
    headA.next.next.next.next = create(3);
    headA.next.next.next.next.next = create(5);
    headA.next.next.next.next.next.next = create(7);
    headA.next.next.next.next.next.next.next = create(7);

    headA = deleteDuplicates(headA);
    printLinkedList(headA);
  }
}
1 3 5

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين) ، ڇاڪاڻ ته اسان عناصر کي هڪ ئي ڪري رهيا آهيون. ان ڪري وقت جي پيچيدگي سڌي آهي.

خلائي پيچيدگي

اي (1) ، ڇاڪاڻ ته اسان مسلسل عنصر استعمال ڪيا آهن. اھڙيءَ طرح خلائي پيچيدگي مستقل آھي.