C++实现单链表删除倒数第k个节点的方法
本文实例讲述了C++实现单链表删除倒数第k个节点的方法。分享给大家供大家参考，具体如下：
题目：
删除单链表中倒数第k个节点
解题思路及算法代码：
标尺法，定义两个指针指向链表头结点，先让一个走k步，然后两个指针同时开始走，当先走的指针走到末尾时，后走的指针指向的结点就是需要删除的结点。
单链表结构定义：
typedef struct Node
{
int data;
struct Node* next;
}node, *pLinkedList;
删除倒数第K结点操作代码：
//head表示头结点
Node* removeLastKthNode(pLinkedList head, int k)
{
if (NULL == head->next || k < 1)
return head;
pLinkedList cur = head; //1号指针
pLinkedList ret = head; //2号指针，指向待删除节点
pLinkedList pre = NULL; //pdel待删除节点的前一个节点
/*
head 1 2 3 4 5
cur
ret
*/
while (k > 0 && cur != NULL)
{
k--;
cur = cur->next;
}
//当链表走到终点时，k仍然大于0，可知k值大于链表长度
if (k > 0 && cur == NULL)
{
cout << "k值大于链表长度" << endl;
return head;
}
//k == 0时，1号指针和2号指针同时走,ret即为待删除的节点
if (k == 0)
{
while (cur != NULL)
{
pre = ret;
cur = cur->next;
ret = ret->next;
}
/*k = 2时
head 1 2 3 4 5 NULL
pre ret cur
即要求删除ret节点
*/
pre->next = ret->next;
free(ret);
ret = NULL;
return head;
}
}
希望本文所述对大家C++程序设计有所帮助。
相关推荐
-
C++中单链表的建立与基本操作
准备数据 准备在链表操作中需要用到的变量及数据结构 示例代码如下: 复制代码 代码如下: struct Data //数据结点类型 { string key; //关键字 string name; int age;};struct CLType //定义链表结构 { Data nodeData; Data *nextNode;}; 定义了链表数据元素的类型Data以及链表的数据结构CLType.结点的具体数据保存在一个结构Data中,而指针nextNode用来指向下一个结点. 我们可以
-
C++ 单链表的基本操作(详解)
链表一直是面试的高频题,今天先总结一下单链表的使用,下节再总结双向链表的.本文主要有单链表的创建.插入.删除节点等. 1.概念 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素. 链表中的数据是以结点来表示的,每个结点的构成:元素 + 指针,元素就是存储数据的存储单元,指针就是连接每个结点的地址数据.如下图: 2.链表的基本操作 SingleList.cpp: #include "stdafx.h" #include "SingleList.h&
-
利用C++简单实现顺序表和单链表的示例代码
本文主要给大家介绍了关于C++实现顺序表和单链表的相关内容,分享出来供大家参考学习,话不多说,来一起看看详细的介绍: 一.顺序表示例代码: #include <assert.h> #include <iostream> using namespace std; typedef int Datatype; class SeqList { public: SeqList() :_array(NULL) ,_size(0) ,_capacity(0) { } SeqList(const
-
如何在C++中建立一个顺序表
准备数据 复制代码 代码如下: #define MAXLEN 100 //定义顺序表的最大长度struct DATA{ char key[10]; //结点的关键字 char name[20]; int age;};struct SLType //定义顺序表结构 { DATA ListData[MAXLEN+1];//保存顺序表的结构数组 int ListLen; //顺序表已存结点的数量 }; 定义了顺序表的最大长度MAXLEN.顺序表数据元素的类型DATA以及顺序表的数据结构SLTyp
-
C++实现顺序表的常用操作(插入删出查找输出)
实现顺序表的插入,删除,查找,输出操作在C语言中经常用到.下面小编给大家整理实现代码,一起看下吧 代码如下所示: #include<iostream> using namespace std; #define MAXSIZE 15 typedef int DataType; typedef struct { DataType data[MAXSIZE]; //通常用一位数组来描述顺序表的数据存储 int SeqLength; /*线性表长度*/ } SeqList; SeqList *Init
-
C++实现单链表按k值重新排序的方法
本文实例讲述了C++实现单链表按k值重新排序的方法.分享给大家供大家参考,具体如下: 题目要求: 给定一链表头节点,节点值类型是整型. 现给一整数k,根据k将链表排序为小于k,等于k,大于k的一个链表. 对某部分内的节点顺序不做要求. 算法思路分析及代码(C) 思路:将链表分为小于k.等于k.大于k的三个链表,然后再合并. 链表结点定义: typedef struct Node { int data; struct Node* next; }node, *pNode; 算法代码: pNode s
-
C++ 实现静态单链表的实例
C++ 实现静态单链表的实例 利用数组实现的静态单链表,与严蔚敏书实现略有不同,不另设回收空间.有任何BUG或错误,希望各位朋友多多反馈~~感激不尽 /* Author : Moyiii * Mail: lc09@vip.qq.com * 静态链表实现,仅作学习之用,当然如果 * 你想拿去用,随你好啦. */ #include <iostream> using namespace std; #define MAX_LIST_SIZE 100 class Node { public: int d
-
C++实现顺序表的方法
废话不多说了,直接给大家上关键代码了. #pragma once #include <assert.h> template<class T> class SeqList { public: SeqList() :_a(NULL) ,_size(1) ,_capacity(1) {} SeqList(T* a, size_t size) :_a(new T[size]) ,_size(size) ,_capacity(size) { for (size_t i = 0; i <
-
浅析C++中单链表的增、删、改、减
首先是是一个简单的例子,单链表的建立和输出.程序1.1 复制代码 代码如下: #include<iostream>#include<string>using namespace std;struct Student{ string name; string score; Student *next;//定义了指向Candidate类型变量的指针};int main(){ int n;// cout<<"请输入学生的总数:"; cin>>n
-
C++实现单链表删除倒数第k个节点的方法
本文实例讲述了C++实现单链表删除倒数第k个节点的方法.分享给大家供大家参考,具体如下: 题目: 删除单链表中倒数第k个节点 解题思路及算法代码: 标尺法,定义两个指针指向链表头结点,先让一个走k步,然后两个指针同时开始走,当先走的指针走到末尾时,后走的指针指向的结点就是需要删除的结点. 单链表结构定义: typedef struct Node { int data; struct Node* next; }node, *pLinkedList; 删除倒数第K结点操作代码: //head表示头结
-
PHP获取链表中倒数第K个节点的方法
本文实例讲述了PHP获取链表中倒数第K个节点的方法.分享给大家供大家参考,具体如下: 问题 输入一个链表,输出该链表中倒数第k个结点. 解决思路 注意这个题目是返回节点,而不是返回值.返回值的话可以用栈来存储.返回节点则不能这样做. 设置两个指针,先让第一个指针移动k-1次.然后两个指针同时移动,当第一个指针到达最后一个节点,第二个指针就在倒数第k个节点. 注意边界:K长度可能超出链表长度,所以当第一个指针的next为空时,返回null 实现代码 <?php /*class ListNode{
-
python实现单链表中删除倒数第K个节点的方法
本文实例为大家分享了python实现单链表中删除倒数第K个节点的具体代码,供大家参考,具体内容如下 题目: 给定一个链表,删除其中倒数第k个节点. 代码: class LinkedListAlgorithms(object): def __init__(self): pass def rm_last_kth_node(self, k, linked_list): # 删除倒数第 K 个节点,针对单链表的 if linked_list.is_empty(): print 'The given li
-
C语言实现输出链表中倒数第k个节点
本文实例展示了C++实现输出链表中倒数第k个节点的方法,分享给大家供大家参考之用. 运行本文所述实例可实现输入一个单向链表,输出该链表中倒数第k个节点. 具体实现方法如下: /* * Copyright (c) 2011 alexingcool. All Rights Reserved. */ #include <iostream> using namespace std; int array[] = {5, 7, 6, 9, 11, 10, 8}; const int size = size
-
如何利用Java输出链表中倒数第k个结点
目录 前言 问题描述 方法一 方法描述 动画演示 代码如下 方法二 方法描述 动画演示 代码如下 总结 前言 链表是一种数据结构,和数组同级.比如,Java中我们使用的ArrayList,其实现原理是数组.而LinkedList的实现原理就是链表了.链表在进行循环遍历时效率不高,但是插入和删除时优势明显 本文主要介绍的是输出链表中倒数第k个结点,下面来一起看看详细的介绍吧 问题描述 给你一个单链表,输出倒数第k个结点,如下图链表中,输出倒数第k个结点,比如 k = 2,输出5这个结点. 方法一
-
Java输出链表倒数第k个节点
问题描述 输入一个链表,输出该链表中倒数第k个结点.(尾结点是倒数第一个) 结点定义如下: public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } 思路1: 先遍历链表,计算其长度length; 然后计算出倒数第k个结点就是正数第length - k + 1. 最后再遍历链表,找到所求结点 时间复杂度O(2n),需要遍历两次链表 代码如下: public List
-
C语言中如何实现单链表删除指定结点
目录 单链表删除指定结点 链表的删除结点(各种方法) 链表中删除第i个结点 删除与链表中与a相同的结点 删除链表中重复元素 单链表删除指定结点 在单链表中删除指定的结点.这里单链表是用尾插法建立的,因为尾插法输出的顺序与输入的顺序是相同的. #include <bits/stdc++.h> using namespace std; typedef struct node { int data; struct node *next; }no; int main() { no *head,*tai
-
angular动态删除ng-repaeat添加的dom节点的方法
本文介绍了angular动态删除ng-repaeat添加的dom节点的方法,分享给大家供大家参考,具体如下: 通过点击删除按钮删除数据库信息以及当前行 html代码如下: <div class="row"> <div class="col-xs-12"> <!-- PAGE CONTENT BEGINS --> <div class="row"> <div class="col-xs
-
删除javascript所创建子节点的方法
本文实例讲述了删除javascript所创建子节点的方法.分享给大家供大家参考.具体如下: js创建的节点,一时不知道如何删除...耗了一大堆时间 for(var i = 0; i < jsonList.length; i++ ){ var li_button = document.createElement("li"); li_button.className = "button"; var li_button_a = document.createElem
-
Java实现双链表互相交换任意两个节点的方法示例
本文实例讲述了Java实现双链表互相交换任意两个节点的方法.分享给大家供大家参考,具体如下: 概述: 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 思路: 1.确定两个节点的先后顺序 2.next.prev互相交换顺序以及将换向前方的节点与之前的节点对接.(1.prev.next = 2) 3.判断是否相邻 实现代码: 链表类: publi