C++删除链表中间节点的方法

2020-01-26 14:09:51

字体：大中小

来源：转载

供稿：网友

本文实例讲述了C++删除链表中间节点的方法。分享给大家供大家参考，具体如下：

题目：

给定链表头结点head，实现删除链表的中间节点函数。

解题思路及代码：

快慢指针，快指针走两步，慢指针一步。
当快指针走到终点时，慢指针正好是链表中间节点，删除此节点即可。

链表结构定义：

typedef struct Node{  int data;  struct Node* next;}node, *pLinkedList;

算法C++代码：

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个节点  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;  }  //此时fast已到终点，slow为中间节点，pre为中间节点前一个节点  pre->next = slow->next;  free(slow);  slow = NULL;  return head;}

希望本文所述对大家C++程序设计有所帮助。

上一篇：C++实现单链表删除倒数第k个节点的方法

下一篇：C++基于先序、中序遍历结果重建二叉树的方法