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

本文实例讲述了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++程序设计有所帮助。

赞 (0)

相关推荐

  • C++ 实现静态链表的简单实例

    C++ 实现静态链表的简单实例

    C++ 实现静态链表的简单实例 用数组描述的链表,即称为静态链表. 在C语言中,静态链表的表现形式即为结构体数组,结构体变量包括数据域data和游标cur. 这种存储结构,仍需要预先分配一个较大的空间,但在作为线性表的插入和删除操作时不需移动元素,仅需修改指针,故仍具有链式存储结构的主要优点. 下图表示了静态链表的一中存储结构: 图中用彩色途上的是两个头结点,不存放数据,分别用来记录第一个备用节点和第一个数据节点的下标. 下面给出静态链表的C++实现代码: 首先给出头文件:StaticList.

  • 深入解析C++的循环链表与双向链表设计的API实现

    深入解析C++的循环链表与双向链表设计的API实现

    循环链表设计与API实现 基本概念 循环链表的定义:将单链表中最后一个数据元素的next指针指向第一个元素 循环链表拥有单链表的所有操作 创建链表 销毁链表 获取链表长度 清空链表 获取第pos个元素操作 插入元素到位置pos 删除位置pos处的元素 新增功能:游标的定义 在循环链表中可以定义一个"当前"指针,这个指针通常称为游标,可以通过这个游标来遍历链表中的所有元素. 循环链表新操作 将游标重置指向链表中的第一个数据元素 CircleListNode* CircleList_Res

  • 关于双向链表的增删改查和排序的C++实现

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 由于双向链表可以方便地实现正序和逆序两个方向的插入.查找等功能,在很多算法中经常被使用, 这里用C++构造了一个双向链表,提供了对双向链表的插入.查找.删除节点.排序等功能,其中排序提供了插入排序和冒泡排序两种方式 #include<iostream> using namespace std;

  • C++ 中循环链表和约瑟夫环

    循环链表和约瑟夫环 循环链表的实现 单链表只有向后结点,当单链表的尾链表不指向NULL,而是指向头结点时候,形成了一个环,成为单循环链表,简称循环链表.当它是空表,向后结点就只想了自己,这也是它与单链表的主要差异,判断node->next是否等于head. 代码实现分为四部分: 初始化 插入 删除 定位寻找 代码实现: void ListInit(Node *pNode){ int item; Node *temp,*target; cout<<"输入0完成初始化"&

  • C++ 双链表的基本操作(详解)

    C++ 双链表的基本操作(详解)

    1.概念 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 结构图如下所示: 2.基本操作实例 DoubleList.cpp #include "stdafx.h" #include "DoubleList.h" #include <stdio.h> #include <malloc.h>

  • C++实现的链表类实例

    本文实例讲述了C++实现的链表类.分享给大家供大家参考.具体如下: #include <iostream> using namespace std; class linklist { private: struct node { int data; node *link; }*p; public: linklist(); void append( int num ); void add_as_first( int num ); void addafter( int c, int num );

  • C++将二叉树转为双向链表及判断两个链表是否相交

    C++将二叉树转为双向链表及判断两个链表是否相交

    把二叉查找树转变成排序的双向链表 例如: 转换成双向链表 4=6=8=10=12=14=16 struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 首先阐述下二叉排序树: 它首先要是一棵二元树,在这基础上它或者是一棵空树:或者是具有下列性质的二元树: (1)若左子树不空

  • C++ 数据结构链表的实现代码

    C++ 数据结构链表的实现代码

    C++ 链表 之前一直没怎么在意C++中的链表,但是突然一下子让自己写,就老是出错.没办法,决定好好恶补一下该方面的知识,也为今后的数据结构大下个良好的基础,于是我总结出以下几点,有些地方可能不正确,还望大家不吝赐教,旨在共同进步. 总结: 1.链表List的基本单元是节点Node,因此想要操作方便,就必须为每一步打好基础,Node的基本结构如下: class Node{ public: int data; Node *next; Node(int da=0,Node *p=NULL){ thi

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

    本文实例讲述了C++删除链表中间节点的方法.分享给大家供大家参考,具体如下: 题目: 给定链表头结点head,实现删除链表的中间节点函数. 解题思路及代码: 快慢指针,快指针走两步,慢指针一步. 当快指针走到终点时,慢指针正好是链表中间节点,删除此节点即可. 链表结构定义: typedef struct Node { int data; struct Node* next; }node, *pLinkedList; 算法C++代码: Node* removeMidNode(pLinkedList

  • PHP实现双链表删除与插入节点的方法示例

    本文实例讲述了PHP实现双链表删除与插入节点的方法.分享给大家供大家参考,具体如下: 概述: 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 实现代码: <?php class node{ public $prev; public $next; public $data; public function __construct($data,$

  • C++实现LeetCode(237.删除链表的节点)

    [LeetCode] 237.Delete Node in a Linked List 删除链表的节点 Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with va

  • Java剑指offer之删除链表的节点

    目录 1.简述 2.代码实现 1.简述 描述: 给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点.返回删除后的链表的头节点. 1.此题对比原题有改动 2.题目保证链表中节点的值互不相同 3.该题只会输出返回的链表和结果做对比,所以若使用 C 或 C++ 语言,你不需要 free 或 delete 被删除的节点 数据范围: 0<=链表节点值<=10000 0<=链表长度<=10000 示例1 输入: {2,5,1,9},5 返回值: {2,1,9} 说明: 给定你链

  • jQuery插件zTree实现删除树子节点的方法示例

    jQuery插件zTree实现删除树子节点的方法示例

    本文实例讲述了jQuery插件zTree实现删除树子节点的方法.分享给大家供大家参考,具体如下: 1.实现代码: <!DOCTYPE html> <html> <head> <title>zTree实现基本树</title> <meta http-equiv="content-type" content="text/html; charset=UTF-8"> <link rel="

  • java使用归并删除法删除二叉树中节点的方法

    本文实例讲述了java使用归并删除法删除二叉树中节点的方法.分享给大家供大家参考.具体分析如下: 实现的思想很简单: first:找到要删除的节点 second:如果删除的节点没有右子树那么左子树链到父节点 third:如果删除的节点没有左子树那么右子树链到父节点 forth:如果删除的节点又左右孩子,那么可以归并删除节点后的子树:方法有两种一种是用删除节点的左子树的最右节点,指向删除节点的右子树,另一种是用删除节点的用字数的最左节点指向删除节点的左子树. Java 实现如下: public v

  • Javascript删除指定元素节点的方法

    在javascript操作dom树的时候可能会经常遇到增加,删除节点的事情,比如一个输入框后一个增加按钮,一个删除按钮,点击增加就增加 个输入框,点击删除就删除对应的输入框.在一些js框架,如Prototype中,可以用element.remove()来删除一个节点,核心JS中并 没有这样的方法,IE中有这样一个方法:removeNode(),尝试运行下面的代码 <div><input onclick="removeNode(this)" type="tex

  • 基于Python和C++实现删除链表的节点

    给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点. 返回删除后的链表的头节点. 示例 1: 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9. 示例 2: 输入: head = [4,5,1,9], val = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 ->

  • PHP获取链表中倒数第K个节点的方法

    本文实例讲述了PHP获取链表中倒数第K个节点的方法.分享给大家供大家参考,具体如下: 问题 输入一个链表,输出该链表中倒数第k个结点. 解决思路 注意这个题目是返回节点,而不是返回值.返回值的话可以用栈来存储.返回节点则不能这样做. 设置两个指针,先让第一个指针移动k-1次.然后两个指针同时移动,当第一个指针到达最后一个节点,第二个指针就在倒数第k个节点. 注意边界:K长度可能超出链表长度,所以当第一个指针的next为空时,返回null 实现代码 <?php /*class ListNode{

  • 给定链表中间节点指针，删除中间节点的方法

    问题如下输入:链表 a->b->c->d->e中指向节点c的指针输出:无返回值,但新链表变为a->b->d->e解答:想了好久没想出来,看了提示才知道解法的.这里用到了一个小技巧.要删除中间节点,但是我们不知道要删除节点的上一个节点p,所以无法通过修改指针的方法(p->next=del->next)来删除节点,但知道要删除节点的后一个节点,那么我们换一个思路,把要删除的节点的数据与该节点的后一个节点的数据交换,然后删除后一个节点,从而达到目的.但是该方

随机推荐