1. 在一个单向链表中,寻找链表中间节点。
使用两个指针,快指针每次步进为2,慢指针每次步进为1。当快指针到达链表尾部时,慢指针指向的就是链表的中间。
Node findMiddleNode(Node head) {
if (head == null)
return head;
Node p1 = head;
Node p2 = p1.next;
while (p2 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
return p1;
}
2. 在单向链表中寻找倒数第n个元素
思路同1,使用两个指针,它们之间保持n的距离,当第一个指针到达链表尾部时,第二个指针指向的就是链表的倒数第n个元素。
Node findLastNNode(Node head, int n) {
Node p1 = head;
Node p2 = head;
int i;
for (i = 0; p1 != null && i < n; i++) {
p1 = p1.next;
}
if (i != n)
return null; // 链表长度小于n
while (p1 != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
3. 判定链表中是否存在环
思路同1,使用两个指针,p1每次步进为2,p2每次步进为1,循环直到p2等于null或者两个指针相等。若p2==null,说明该链表不存在环;若p1==p2,说明存在环。
bool isLoop(Node head) {
if (head == null)
return false;
Node p1 = head;
Node p2 = p1.next;
while (p2 != null && p2.next != null && p1 != p2) {
p1 = p1.next;
p2 = p2.next.next;
}
if (p1 == p2)
return true;
else
return false;
}
分享到:
相关推荐
1.随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。 2.遍历单向链表。 3.把单向链表中元素逆置(不允许申请新的结点空间)...利用算法5建立两个非递减有序单向链表,然后合并成一个非递增链表。
04.单向链表以及单向链表的应用.ppt
C#单向链表的实现的源码
单向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 作者Clifford A.Shaffer 重庆大学使用教材
数据结构,c语言实现的单向链表。代码分享 struct LinkNode { int data; struct LinkNode *next; }; typedef struct LinkNode *Lnode;
链表结点插入算法
#资源达人分享计划#
已知head指向一个带头结点的单向链表, 链表中每个结点包含数据域(data)和指针域(next)。 请编写函数实现如图所示链表逆置
一个java实例,用来描述java算法中链表的使用。
每敲一次代码都会有新的收获,基本功不扎实啥也干不了。单向链表的插入,删除,创建,遍历是数据结构的基本操作。里边的算法值得学习。下面我们就来学习一下单向链表结点的逐个删除的方法。
链表逆置是计算机科学中一个重要的算法问题,它涉及到链表数据结构的操作和算法设计。在本文中,我们将详细讨论...链表可以分为单向链表、双向链表和循环链表等不同类型,但在链表逆置问题中,我们通常讨论单向链表。
从键盘输入若干整数,直到输入0时停止,按输入整数顺序建立单向链表存储结构。然后用字符界面菜单提供以下功能: 1.插入元素--输入i, e,在单向链表第i个元素之前插入元素e,输出插入e后的单向链表(已知有效的插入...
利用单链表实现基排序算法
仅遍历一次单向链表,找出中间结点,经典C算法,
单向链表的存储特点及其实现,单向链表的插入 删除算法及其应用算法的程序实现
各种数据结构、算法及实用的C#源代码.C#,单向链表(Simply Linked List)快速排序(Quick Sort)算法与源代码.单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部...
西南交通大学 数据结构实验报告 单向链表 参考解答
栈是基本的数据结构。其特点是添加和访问数据都在线性表的一端(头端)。数据访问遵循先进后出(FILO)的原则。...本程序用单向链表实现栈。是C++、数据结构及算法学习的一个小小练习。供大家参考。
本程序采用指向指针的指针来完成单链表的各种操作 插入、删除、逆转、按地址排序、递归的归并算法
单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。 表元素域elem用来存放具体...