首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

DS单链表--结点交换 C++

题目描述 用C++实现含头结点的单链表,然后实现单链表的两个结点交换位置。...注意不能简单交换两个结点包含数据,必须通过修改指针来实现两个结点的位置交换 交换函数定义可以参考: swap(int  pa, int pb)  //pa和pb表示两个结点在单链表的位置序号 swap...输出 第一行输出单链表创建后的所有数据,数据之间用空格隔开 第二行输出执行第1次交换操作后的单链表数据,数据之间用空格隔开 第三行输出执行第2次交换操作后的单链表数据,数据之间用空格隔开 如果发现输入位置不合法...int data; ListNode * next; ListNode() { data = -9999, next = NULL; } }; class LinkList { //带头结点的单链表...,位置从0到n,0是头结点,1是首结点,n是尾结点 private: ListNode * head; //头结点 int size; //表长 public: LinkList();

20320
您找到你想要的搜索结果了吗?
是的
没有找到

Java 链表结点插入

PS:链表是一种数据结构,而数据结构就是一种存放数据的方式。 为什么需要链表? 我们知道,数组也可以存储数据,那么为什么还需要链表呢?...接下来,我们来看看数组 和链表的区别: 1、数组就像身上编了号站成一排的人,要找第10个人很容易,根据人身上的编号很快就能找到。...链表示意图 链表的建立 class TestLink{//创建一个外部类 private Entry head;//指向头结点的引用 public TestLink(){ head =...new Entry();//用结点类 new 一个头结点 } class Entry{//Entry 创建一个结点内部类 int data;//定义数据块 Entry next;//...= null){ cur = cur.next; } Entry entry = new Entry(val);//得到的结点 cur.next = entry; } //得到单链表的长度

47910

链表中环的入口结点

题目描述 给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。 解题思路 一种方法是用 hashmap来存储和查找节点; 另一种方法是双指针法。...假设环长度为n,进入环之前结点个数为x,slow在环内走了k个结点,fast绕环走了m圈,则有2(x+k)=x+mn+k 可以得出x = mn - k。...此时slow距入口结点还剩 n-k个结点,x=(m−1)n+n−k,即一个指针从链表头节点走到环入口的长度等于另一个指针从相遇的位置走 m-1圈后再走n-k的长度,也就是说两个指针相遇后,让一个指针回到头节点...所以,我们设置两个指针,一个是快指针fast,一个是慢指针slow,fast一次走两步,slow一次走一步,如果单链表有环那么当两个指针相遇时一定在环内。...此时将一个指针指到链表头部,另一个不变,二者同时每次向前移一格,当两个指针再次相遇时即为环的入口节点。如果fast走到null则无环。

61930

链表中环的入口结点

解题描述 方法1 - 哈希法,需要额外空间 1、遍历单链表的每个结点 2、如果当前结点地址没有出现在set中,则存入set中 3、否则,出现在set中,则当前结点就是环的入口结点 4、整个单链表遍历完...遍历整个链表结点 空间复杂度O(N):其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。...1、初始化:快指针fast指向头结点, 慢指针slow指向头结点 2、让fast一次走两步, slow一次走一步,第一次相遇在C处,停止 3、然后让fast指向头结点,slow原地不动,让后fast...,slow每次走一步,当再次相遇,就是入口结点。...在最初判断快慢指针是否相遇时,slow 指针走过的距离不会超过链表的总长度;随后寻找入环点时,走过的距离也不会超过链表的总长度 空间复杂度O(1):额外使用的指针占用常数空间

52020

链表、头指针、头结点

头指针 指示链表中第一个结点(即第一个数据元素的存储映像)的存储位置。同时,由于最后一个数据元素没有直接后继,则线性链表中最后一个结点的指针为“空”(NULL)。 ?..., *LinkList;   有时在单链表的第一个结点之前附设一个结点,称之为头结点 。...若线性表为空,则头结点的指针域为“空”,如图2(b)所示。 ? 图2 带头结点的单链表   (a)非空表;(b)空表 循环链表 是另一种形式的链式存储结构。...它的特点是表中最后一个节点的指针域指向头结点,整个链表形成一个环。由此,从表中任一结点出发均可找到表中其他结点,如图3所示为单链的循环链表 。 ?...图5 双向链表示例 (a)结点结构;(b)空的双向循环链表;(c)非空的双向循环链表

1.2K70

链表篇】LeetCode 876、链表的中间结点

一、题目描述 给定一个头结点为 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。...示例 1: 输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。...示例 2: 输入:[1,2,3,4,5,6] 输出:此列表中的结点 4 (序列化形式:[4,5,6]) 由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。...提示: 给定链表结点数介于 1 和 100 之间。 二、题目解析 我个人认为这道题目是最好理解快慢指针这个知识点了。 废话不多说,直接先来看动画演示!...三、参考代码 // LeetCode 100 题精讲:https://mp.weixin.qq.com/s/yznC53g46phq3qF7V4-obA // 作者:程序员吴师兄 // 链表的中间结点

20750

刷LeetCode链表之前你需要掌握的设置结点技巧C++

c++的线性表中,如何用ListNode设置好结点呢?...我们往往因为不熟悉指针和内存分配的原理,而在初学阶段不能正确的设置好结点,我总结了俩种不同情况设置结点的情况,这里引用LeetCode的几个题目为例 一、设置一个结点指向头结点head 如:ListNode...* p  = head; 在这里面我们设置了一个结点指向head,我们用它可以帮助我们遍历整个链表c++中如果我们需要求一个链表的长度时时候就可以这样设置 剑指 Offer 22....这一道题你在求解过程需要求链表长度 ,通过ListNode *pre = head;设置pre这个结点可以帮助遍历链表 class Solution { public: ListNode* getKthFromEnd...合并两个有序链表 题解 C++ [链表]leetcode725-分隔链表C++) (如果本篇文章有错误的地方,请及时指正,感谢你的阅读)

20240

链表中倒数第k个结点 链表中倒数第k个结点

题目描述 输入一个链表,输出该链表中倒数第k个结点。 解题思路 经典的双指针法。...定义两个指针,第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针保持不动,从第k步开始,第二个指针也开始从链表的头指针开始遍历,由于两个指针的距离保持在k-1,当第一个指针到达链表的尾节点时,第二个指针刚好指向倒数第...链表头指针是否为空,若为空则直接返回回null 2. k是否为0,k为0也就是要查找倒数第0个节点,由于计数一般是从1开始的,所有输入0没有实际意义,返回null 3. k是否超出链表的长度,如果链表的节点个数少于...if(head == null || k == 0) return null; ListNode temp = head; //判断k是否超过链表节点的个数...pA = pA.next; pB = pB.next; } return pB; } } 当然,还有一种是用stack的方法,把链表按顺序压入

43620

LeetCode:链表的中间结点_876

思路 一次遍历链表,寻找中间节点。两个信息,一、要遍历完,二、遍历完时需要遍历到中间节点。所以需要两个指针,并且速度是1:2。注意题目要求中点为两个时,取后面个。...题目 给定一个头结点为 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。...示例 1: 输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。...示例 2: 输入:[1,2,3,4,5,6] 输出:此列表中的结点 4 (序列化形式:[4,5,6]) 由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。...提示: 给定链表结点数介于 1 和 100 之间。

24920

链表的中间结点

链表的中间结点 链接 链表的中间结点 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。...示例 1: 输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。...示例2: 输入:[1,2,3,4,5,6] 输出:此列表中的结点 4 (序列化形式:[4,5,6]) 由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。...提示: 给定链表结点数介于 1 和 100 之间。...解题思路 定义一个快指针fast 一个慢指针slow ,快指针一次移动两个结点,慢指针一次移动一个结点 当fast到达链表的尾部结点时,慢指针也就移动到了链表的中间结点(同化成一个路程问题,同一段路程,

64830

反转链表 & 876. 链表的中间结点

反转链表 力扣题目链接[1] 给你单链表的头节点 head,请你反转链表,并返回反转后的链表。...最终pre的指向就是翻转前链表的尾部节点,也是翻转后链表的头部,返回pre即可。 链表 /** * Definition for singly-linked list....链表的中间结点 力扣题目链接[2] 给定一个头结点为 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。...示例 2: 输入:[1,2,3,4,5,6] 输出:此列表中的结点 4 (序列化形式:[4,5,6]) 由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。...包括寻找链表的中间节点、检查链表是否存在环。都需要重点掌握。复杂度方面,时间复杂度是链表长度的一半,也就是O(n),维护了两个常数级别的变量,因此空间复杂度是O(1)。

27610
领券