notepad++節點

Given a single Linked List and we have to delete the middle the element of the Linked List.

給定一個鏈表，我們必須刪除鏈表中間的元素。

If the length of the linked list is odd then delete (( n+1)/2)th term of the linked list and if the list is of even length then delete the (n/2+1)th term of the liked list.

如果鏈接列表的長度為奇數，則刪除鏈接列表的第((n + 1)/ 2)項；如果列表的長度為偶數，則刪除喜歡列表的第(n / 2 + 1)項。

Example 1:

范例1：

    If we have a Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7
After deleting the middle node the linked list will be: 
1 → 2 → 3 → 5 → 6 → 7 
4 is the middle node

Example 2:

范例2：

    If we have a Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
After deleting the middle node the linked list will be: 
1 → 2 → 3 → 4 → 6 → 7 → 8
5 is the middle node

Algorithm:

算法：

To solve the problem we follow the following procedure,

為了解決該問題，我們遵循以下過程，

1. We initiate the two node pointer name as slow, fast. (like Floyd's tortoise algo, refer the link to my article of merge sort in the linked list).

   我們將兩個節點的指針名稱初始化為慢，快。 (就像弗洛伊德(Floyd)的烏龜算法一樣，請在鏈接列表中引用我的合并排序文章的鏈接)。

2. Each time we increment the slow by one whereas increment the fast pointer by two.

   每次我們將慢速指針加一，而快速指針加二。

3. Repeat step 2 until the fast pointer goes to the end of the linked list.

   重復步驟2，直到快速指針移到鏈接列表的末尾。

4. When fast pointer goes to the end of the list at the same time slow pointer points to the middle of the linked list.

   當快速指針同時到達列表末尾時，慢速指針指向鏈接列表的中間。

5. Then delete the middle node.

   然后刪除中間節點。

C++ implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
struct node{
int data;
node* next;
};
//Create a new node
struct node* create_node(int x){
struct node* temp= new node;
temp->data=x;
temp->next=NULL;
return temp;
}
//Enter the node into the linked list
void push(node** head,int x){
struct node* store=create_node(x);
if(*head==NULL){
*head =store;
return;
}
struct node* temp=*head;
while(temp->next){
temp=temp->next;
}
temp->next=store;
}
//Delete the middle node from the linked list
void delete_node(node** head){
if((*head)->next==NULL){
*head=NULL;
return;
}
struct node* fast=(*head)->next;
struct node* slow=*head;
while(fast && fast->next && fast->next->next){
slow=slow->next;
fast=fast->next->next;
}
slow->next=slow->next->next;
}
//Print the list
void print(node* head){
struct node* temp=head;
while(temp){
cout<<temp->data<<" ";
temp=temp->next;
}
}
int main()
{
struct node* l=NULL;
push(&l,1);
push(&l,2);
push(&l,3);
push(&l,4);
push(&l,5);
push(&l,6);
cout<<"Before the delete operation"<<endl;
print(l);
delete_node(&l);
cout<<"\nAfter the delete operation"<<endl;
print(l);
return 0;
}

Output

輸出量

Before the delete operation
1 2 3 4 5 6
After the delete operation
1 2 3 5 6

翻譯自: https://www.includehelp.com/cpp-programs/delete-the-middle-node-of-a-linked-list-in-cpp.aspx

notepad++節點