文档章节

单链表——查找单链表的中间结点

清风傲剑
 清风傲剑
发布于 2014/10/02 14:15
字数 373
阅读 40
收藏 0
package jxau.lyx.sort;

/**
 * 
 * @author: liyixiang
 * @data:2014-10-1
 * @题目大意:
 * 		查找单链表的中间结点
 * @主要思路:
 * 		此题可应用于上一题类似的思想。也是设置两个指针,只不过这里是,
 * 两个指针同时向前走,前面的指针每次走两步,后面的指针每次走一步,        
 * 前面的指针走到最后一个结点时,后面的指针所指结点就是中间结点,
 * 即第(n/2+1)个结点。注意链表为空,链表结点个数为1和2的情况。
 * @时间复杂度:
 * 		时间复杂度O(n)
 * @空间复杂度:
 */
public class GetMiddleNode {

	//结点
	private static class Node {           
		int val;           
		Node next;               
		
		public Node(int val) {               
			this.val = val;          
		}       
	}
			
	public Node getMiddleNode(Node head){
		if(head == null || head.next == null){
			return head;
		}
		
		Node q = head;
		Node p = head;
		
		//前面指针每次走两步,直到指向最后一个结点,后面指针每次走一步 
		while(q.next!=null){
			q = q.next;
			p = p.next;
			
			if(q.next!=null){
				q = q.next;
			}
		}
		
		return p;
	}
		
}


© 著作权归作者所有

清风傲剑
粉丝 31
博文 75
码字总数 40365
作品 0
蚌埠
高级程序员
私信 提问
数据结构——基于java的链表实现(真正理解链表这种数据结构)

原创不易,如需转载,请注明出处https://www.cnblogs.com/baixianlong/p/10759599.html,否则将追究法律责任!!! 一、链表介绍 1、什么是链表? 链表是一种物理存储结构上非连续、非顺序的...

会炼钢的小白龙
04/23
0
0
基本数据结构 -- 链表的遍历、查找、插入和删除单

  本文将使用 C 语言来实现一个单链表,并实现遍历、查找、插入、删除等操作。 一、创建一个单链表   首先,定义一个存放结点相关信息的结构体,结构体有两个元素,分别是键值和一个指向...

tongye
04/23
0
0
链表面试题(上)

一、题目 1、从尾到头打印单链表 (有四种方法) 2、删除一个无头单链表的非尾节点(不能遍历链表) 3、在无头单链表的一个节点前插入一个节点(不能遍历链表) 4、单链表实现约瑟夫环(Joseph...

qq_38646470
2018/01/04
0
0
数据结构和算法之一——线性表_3_链式存储结构_1_单链表

1. 链表的定义 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以存在内存中未被占用的任意位置。 (比起顺序存储结构每个数据元素只需要存储一个位置...

Eric_Hunter
2018/01/11
0
0
Java基础知识——数组与链表的区别

1、数组与链表的区别。 数组是具有相同的数据类型且按一定次序排列的一组变量的集合体,数组在内存中的地址是连续的(链表内存地址是散列、不连续的)。数组是一种引用数据类型,数组元素类似...

小八路2222
03/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Shell学习成果之一键自动安装Mysql8.0

实验环境 系统:CentOS7.7.1908 MySql:mysql-8.0.18-el7-x86_64.tar.gz 一键安装脚本如下(可直接复制粘贴为shell脚本,与MySQL安装包放到同一目录;如果没有下载安装包就取消第26行的注释会...

网络小虾米
31分钟前
4
0
X-MSG-IM-系统依赖的第三方library编译

X-MSG-IM系统核心网元编译时依赖较多第三方库, 较为繁琐. 这是为了在部署时更方便, 更少地依赖宿主系统环境. 除非你知道自己在做什么, 否则不要变更这些库的版本. zlib-1.2.11编译 wget htt...

x-msg-im
今天
6
0
电磁兼容谐波电流测试怎么做?看完这篇文章90%的人都能明白

在正式学习谐波电流测试之前,先给大家分享一个故事: 1807年时年39岁的法国数学家傅里叶于法国科学学会上展示了一篇论文"热的传播"(Mémoire sur la propagation de la chaleur),论文中有个...

demyar
今天
3
0
数据管理必看!Kendo UI for jQuery过滤器的全球化

Kendo UI for jQuery最新试用版下载 Kendo UI目前最新提供Kendo UI for jQuery、Kendo UI for Angular、Kendo UI Support for React和Kendo UI Support for Vue四个控件。Kendo UI for jQue......

FILA6666
今天
4
0
ES6基础入门之let、const

作者 | Jeskson 来源 | 达达前端小酒馆 01 首先呢?欢迎大家来学习ES6入门基础let,const的基础知识内容。初始ECMA Script6。 ESMAScript与JavaScript的关系: ES是JS的标准(ES是对ECMAScr...

达达前端小酒馆
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部