Datenstruktur – verknüpfte Liste.

Feb 09 2023

In diesem Blog werde ich einige Fragen zur Linked List stellen, die mir persönlich dabei geholfen haben, mich damit vertraut zu machen. Wenn Sie über die erforderlichen Kenntnisse in STL, verknüpften Listen und Rekursion verfügen, können Sie diesen auf Problemlösungen ausgerichteten Blog noch besser verstehen.

Persönlich glaube ich, dass die verknüpfte Liste eine der einfachsten Datenstrukturen ist. Aber man muss Logik entwickeln und die Fähigkeit haben, sie zu visualisieren, um knifflige oder schwierige Situationen damit zu meistern.

Ich habe Fragen von der LeetCode-Plattform ausgewählt, die eine der besten Plattformen zur Problemlösung und zum Bewältigen algorithmischer Probleme ist. Ich habe mich nicht mit den Grundlagen befasst, da es im Internet bereits viele Ressourcen dazu gibt. Dieser Blog dient eher der Problemlösung und der Bereitstellung wichtiger Fragen zur verlinkten Liste. Für einige davon habe ich auch Code in der Programmiersprache C++ bereitgestellt.

VERLINKTE LISTE

Ich werde kurz einige Punkte durchgehen, die man beachten muss, wenn man über eine verknüpfte Liste im Allgemeinen nachdenkt. Zunächst muss man wissen, dass eine verknüpfte Liste eine lineare Datenstruktur ist. Anders als in einem Array werden hier Elemente nicht an zusammenhängenden Speicherorten gespeichert. In einer verknüpften Liste werden Elemente mithilfe von Zeigern miteinander verbunden, was uns die Flexibilität gibt, Elemente in einer verknüpften Liste hinzuzufügen, zu entfernen oder einzufügen. Es besteht keine Notwendigkeit, die Größe einer verknüpften Liste zu initialisieren, während dies wie bei einem Array eine Notwendigkeit ist. Es ist schwierig, direkt auf ein Element in einer verknüpften Liste zuzugreifen, da man die verknüpfte Liste durchlaufen muss, um zu diesem Element zu gelangen, anders als in einem Array, wo wir mithilfe eines Index auf jedes Element zugreifen können.

Bildquelle: https://www.alphacodingskills.com/ds/linked-list.php

ZEIGER

Ein Zeiger ist eine Variable, die die Speicheradresse als Wert speichert.

Nehmen wir nun ein paar Beispiele, um zu verstehen, was ein Zeiger ist:

int *ptr = &var; // Adresse der Variablen var dem PTR-Zeiger zuweisen.

char*ptr = &var; // Adresse der Variablen var dem PTR-Zeiger zuweisen.

int*ptr; // 'ptr' ist ein Zeiger, der auf einen Müllwert zeigt.

Pointer(ptr) speichert die Adresse der Variablen(var). Als Beispiel wird eine zufällige Adresse genommen.

Jetzt werde ich einige der LeetCode-Fragen bereitstellen, die eine Person unbedingt lösen sollte, um Logik aufzubauen und knifflige Situationen zu bewältigen.

Meistens kann man Mehrheitsfragen im Zusammenhang mit verknüpften Listen mithilfe des Fast-and-Slow-Pointers-Ansatzes und der In-Place-Umkehr einer verknüpften Liste lösen.

PROBLEME

Schnelle und langsame Zeiger.

ListNode* middleNode(ListNode* head) {
        
        ListNode *slow = head, *fast = head;
        
        while(fast && fast -> next)
            slow = slow -> next
            fast = fast -> next -> next;
        
        return slow;
    }

bool isPalindrome(ListNode* head) {
       
        ListNode *slow = head, *fast = head, *prev, *temp;
       
        while(fast && fast -> next)
            
            slow = slow -> next, fast = fast -> next -> next;
            prev = slow, slow = slow -> next, prev-> next = NULL;

        while(slow)
            temp = slow -> next, slow -> next = prev, prev = slow, slow = temp;
            fast = head, slow = prev;
        while(slow) 
            if(fast -> val != slow -> val) return false;
            else fast = fast -> next, slow = slow -> next;
        return true;
    }

bool hasCycle(ListNode *head) {
 
        if(head == NULL) return false;
        ListNode *fast = head;
        ListNode *slow = head;
        
        while(fast != NULL and fast -> next != NULL) {
            
            fast = fast -> next -> next;
            slow = slow -> next;
            
            if(fast == slow) return true;
        }
        return false;
    }

ListNode *detectCycle(ListNode *head) {

    if(head == NULL || head -> next == NULL) return NULL;
    
    ListNode *slow  = head;
    ListNode *fast  = head;
    ListNode *cycleStart = head;
    
    while(fast -> next and fast -> next -> next) {

        slow = slow -> next;
        fast = fast -> next -> next;

         if(slow == fast) {
            while(slow != cycleStart) {           
                slow  = slow -> next;
                cycleStart = cycleStart -> next;
            }
            return cycleStart;
        }
    }
    return NULL;                              
  }

ListNode* removeElements(ListNode* head, int val) {

        if(head == nullptr) return head;

        while(head != nullptr && head -> val == val) {

            head = head -> next;
        }
        ListNode* curr = head;

        while(curr != nullptr  and curr -> next != nullptr) {

            if(curr -> next -> val == val) {
                curr -> next = curr -> next -> next;
            }
            else
                curr = curr -> next;
        }
        return head;
    }

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

    if(!list1 || list2 && list1 -> val > list2 -> val) 
        swap(list1, list2);

    if(list1) 
        list1 -> next = mergeTwoLists(list1 -> next, list2);
    return list1;
    }

A. Umgekehrt verknüpfte Liste 1

ListNode* reverseList(ListNode* head) {
     
        ListNode* nextNode;
        ListNode* prevNode = NULL;
        
        while(head) {
            nextNode = head -> next;
            head -> next = prevNode;
            prevNode = head;
            head = nextNode;
        }
        return prevNode;
    }

Das sollten Sie selbst ausprobieren. Dies ist die Erweiterung des oben angegebenen Problems.

C. Knoten in einer verknüpften Liste austauschen

ListNode* swapNodes(ListNode* head, int k) {

        ListNode* temp = head;
        int cnt = 0;
        while(temp) {
            cnt++;
            temp = temp -> next;
        }
        ListNode *start = head, *end = head;

        int s = k - 1, e = cnt - k;

        for(int i = 0; i < s; i++)
            start = start -> next;
        for(int i = 0; i < e; i++)
            end = end -> next;
        
        swap(start -> val, end -> val);
        return head;
    }

void reorderList(ListNode* head) {
        if((!head) || (!head -> next) || (!head -> next -> next)) return;//Edge Cases
        
        stack<ListNode*> st;
        ListNode* temp = head;
        int size = 0;
        while(temp != NULL) {
            st.push(temp);
            size++;
            temp = temp -> next;
        }
        ListNode* ptr = head;
        for(int j = 0; j < size/2; j++)//Between every two nodes insert the one in the top of the stack
        {
            ListNode* element = st.top();
            st.pop();
            element -> next = ptr -> next;
            ptr -> next = element;
            ptr = ptr -> next -> next;
        }
        ptr -> next = NULL;
    }

ListNode* swapPairs(ListNode* head) {
       
        if(head == nullptr || head -> next == nullptr) return head; 

        ListNode* dummy = new ListNode();
        ListNode* prev = dummy;
        ListNode* curr = head;
        
        while(curr and curr -> next) {

            prev -> next = curr -> next;
            curr -> next = prev -> next -> next;
            prev -> next -> next = curr;

            prev = curr;
            curr = curr -> next;
         }
       return dummy -> next;
     }

ListNode* reverseEvenLengthGroups(ListNode* head) {

        if(!head ) return head;

        ListNode* curr = head, *p;
        int sz = 1;
        
        while(curr) {
            
            p = curr;
            vector<int> vec;
            for(int i = 0 ;i < sz && curr != NULL ; i++) {
                vec.push_back(curr -> val);
                curr = curr -> next;    
            }
            if(vec.size() % 2 == 0) {
                reverse(vec.begin(), vec.end());
                for(int i = 0; i < vec.size(); i++){
                    
                    p -> val = vec[i];
                    p = p -> next;    
                }
            }
            sz++;
        }
        return head;
    }

Probieren Sie sie zum besseren Verständnis zunächst selbst aus.

A. Reduzieren Sie den Binärbaum auf eine verknüpfte Liste

void flatten(TreeNode* root) {

        if(root == NULL) return;

        flatten(root -> left);
        flatten(root -> right);

        if(root -> left) {

            TreeNode* right = root -> right;
            root -> right = root -> left;
            root -> left = NULL;

            while(root -> right) 
                 root = root -> right;
                 root -> right = right;
        }
    }

ListNode* rotateRight(ListNode* head, int k) {

        if(head == nullptr || head -> next == nullptr || k == 0)
            return head;
        int len = 1;
        ListNode* tail = head;
        while(tail -> next != nullptr) {
            len++;
            tail = tail -> next;
        }
        tail -> next = head;
        k = len - k % len;

        while(k) {
            tail = tail -> next; 
            k--;
        }
        head = tail -> next;
        tail -> next = nullptr;

        return head;
    }

ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == nullptr) return head;
            ListNode* temp = new ListNode();
            temp -> next = head;
            ListNode* fast = temp;
            ListNode* slow = temp;

            for(int i = 0; i < n; i++) {
                fast = fast -> next;
            }
            while(fast -> next != nullptr) {
                fast = fast -> next;
                slow = slow -> next;
            }
            slow -> next = slow -> next -> next;
            return temp -> next;
    }

ListNode* oddEvenList(ListNode* head) {

        if(!head || !head -> next || !head -> next -> next) 
            return head;

        ListNode* odd_p = head;
        ListNode* even_p = head -> next;
        ListNode* headofeven = even_p;
        
        while(odd_p -> next && even_p -> next) {

            odd_p -> next = odd_p -> next -> next;
            even_p -> next = even_p -> next -> next;

            odd_p = odd_p -> next;
            even_p = even_p -> next;
        }
        odd_p -> next = headofeven;
        return head;
    }

Node* connect(Node* root) {

    if(root == NULL) return NULL;
    //connects the left subtree of same level with right subtree of that same level 
    if(root -> left != NULL) 
         root -> left -> next = root -> right;
    //connect the rightmost node of a level to the leftmost node of the next level.
    if(root -> right != NULL && root -> next != NULL) 
         root -> right -> next = root -> next -> left;
    //recursive calls for left and right subtrees.
    connect(root -> left);
    connect(root -> right);
    return root;
   }

Sie sollten diese Fragen lösen, sobald Sie mit den Problemen mit verknüpften Listen vertraut sind. Diese Fragen werden Ihr Verständnis verschiedener Konzepte im Detail auf die Probe stellen.

A. K sortierte Listen zusammenführen

B. Umkehrknoten in k-Gruppen

C. LFU-Cache

SCHLUSSFOLGERN

Ich habe einige der besten LeetCode-Probleme bereitgestellt, die Ihnen helfen werden, sich mit Linked List vertraut zu machen. Sie sollten immer den LeetCode-Diskussionsbereich besuchen, auch wenn Sie die Frage selbst gelöst haben. Sie lernen verschiedene Codes und Ansätze zur Lösung der Fragen kennen, die für einen Programmierer sehr hilfreich sind.

Nachdem Sie diese gelöst haben, werden Sie auf jeden Fall in der Lage sein, jedes neue Problem zu lösen, auf das Sie bei einem Wettbewerb oder einem Coding-Wettbewerb stoßen könnten. Auch diese Fragen gehören zu den Fragen, die in Vorstellungsgesprächen immer wieder gestellt werden.

Ich habe versucht, einige wichtige Fragen zur Linked List in diesem Blog zusammenzufassen. Ich habe während des Studiums ausführlich über Linked List auf mehreren Plattformen recherchiert und fand diese Fragen am hilfreichsten. Das Wissen um diese Fragen wird Ihnen auf jeden Fall einen Vorteil gegenüber anderen verschaffen.

Anregungen oder konstruktive Kritik sind uns sehr willkommen. Mit diesem Blog überarbeite ich auch meine Konzepte von Datenstrukturen und Algorithmen und versuche, einen Beitrag zur Community zu leisten, was mir überhaupt geholfen hat, es zu lernen.