C++ method to delete the middle node of a linked list
- 2020-05-19 05:14:29
- OfStack
The example in this article shows how to remove the middle node of a linked list by C++. I will share it with you for your reference as follows:
Topic:
Given the header node head, the middle node function of the list can be deleted.
Solution ideas and codes:
Fast pointer, fast pointer two steps, slow pointer 1 step.
When the fast pointer reaches the end point, the slow pointer happens to be the middle node of the linked list, which can be deleted.
List structure definition:
typedef struct Node
{
int data;
struct Node* next;
}node, *pLinkedList;
Algorithm C++ code:
Node* removeMidNode(pLinkedList head)
{
if (head->next == NULL || head == NULL)
return head;
if (head->next->next == NULL)
return head->next;
pLinkedList fast = head;
pLinkedList slow = head;
pLinkedList pre = NULL;
/*
head 1 2 3 4 5
pre slow fast
*/
//1 A node
if (head->next->next == NULL)
return head->next;
while (fast->next != NULL && fast->next->next != NULL)
{
pre = slow;
fast = fast->next->next;
slow = slow->next;
}
// At this time fast We have reached the end, slow Is the intermediate node, pre Is before the intermediate node 1 A node
pre->next = slow->next;
free(slow);
slow = NULL;
return head;
}
I hope this article is helpful to you C++ programming.