Середина запроса заголовка связанного списка - PullRequest
Новая
       21

Середина запроса заголовка связанного списка

0 голосов
/ 17 апреля 2020

В этой программе, когда печатается новый связанный список, как head знает и как эта программа распознает 'prev' и возвращает новый заголовок связанного списка, учитывая его, так как мы не связали head с prev. Первоначально связанный список был

1-> 2-> 3-> 4-> 5

3 удален

, затем

новый связанный список 1- > 2-> 4-> 5

Каков подход к печати этого нового связанного списка. На самом деле я новичок в реализации связанного списка

Как руководитель знает, как связать 'prev' prev->next = slow_ptr->next; к голове. 

// C++ program to delete middle of a linked list 
#include<iostream>
#include<algorithm>
using namespace std; 

/* Link list Node */
struct Node 
{ 
    int data; 
    struct Node* next; 
}; 

// Deletes middle node and returns head of the 
// modified list 
struct Node* deleteMid(struct Node *head) 
{ 
    // Base cases 
    if (head == NULL) 
        return NULL; 
    if (head->next == NULL) 
    { 
        delete head; 
        return NULL; 
    } 

    // Initialize slow and fast pointers to reach 
    // middle of linked list 
    struct Node *slow_ptr = head; 
    struct Node *fast_ptr = head; 

    // Find the middle and previous of middle. 
    struct Node *prev; // To store previous of slow_ptr 
    while (fast_ptr != NULL && fast_ptr->next != NULL) 
    { 
        fast_ptr = fast_ptr->next->next; 
        prev = slow_ptr; 
        slow_ptr = slow_ptr->next; 
    } 

    //Delete the middle node 
    prev->next = slow_ptr->next; 
    delete slow_ptr; 

    return head; 
} 

// A utility function to print a given linked list 
void printList(struct Node *ptr) 
{ 
    while (ptr != NULL) 
    { 
        cout << ptr->data << "->"; 
        ptr = ptr->next; 
    } 
    cout << "NULL\n"; 
} 

// Utility function to create a new node. 
Node *newNode(int data) 
{ 
    struct Node *temp = new Node; 
    temp->data = data; 
    temp->next = NULL; 
    return temp; 
} 

/* Drier program to test above function*/
int main() 
{ 
    /* Start with the empty list */
    struct Node* head = newNode(1); 
    head->next = newNode(2); 
    head->next->next = newNode(3); 
    head->next->next->next = newNode(4); 

    cout << "Gven Linked List\n"; 
    printList(head); 

    head = deleteMid(head); 

    cout << "Linked List after deletion of middle\n"; 
    printList(head); 

    return 0; 
}
...