剑指offer代码解析——面试题15求链表中倒数第K个结点

算法的分析过程均在代码注释中:

/**
 * 题目:输入一个单链表,输出该链表从后往前的第k个数。
 * PS:从后往前数时从1开始计数。
 * @author 柴毛毛大闲人
 */
public class TailK {
	
	/**
	 * 分析:要寻找倒数第k个数,很自然想到的方法是:从末尾向前找第k个数。
	 * 然而这种方法面临两个问题:1.我们无法直到单链表的末尾在哪儿,2.我们无法从后向前遍历单链表。
	 * 为了解决上述两个问题,我们首先想到的方法是:遍历两次单链表,第一次求得单链表的长度n,第二次遍历到第n-k个元素停止即可。
	 * 代码如下:
	 */

	//使用全局变量result表示函数运行结果
	static boolean result = true;
	/**
	 * @param first 单链表的首结点
	 * @param k 要找的倒数第几个元素
	 * @return 返回倒数第K个值
	 */
	public static int getTailK(Node<Integer> first,int k){
		//若链表为空
		if(first==null){
			System.out.println("链表为空!");
			result = false;
			return 0;
		}
		
		//若k<=0
		if(k<1){
			System.out.println("k不能小于1!");
			result = false;
			return 0;
		}
		
		//计算链表长度
		int length = 1;
		Node<Integer> p = first;
		while(p.next!=null){
			length++;
			p = p.next;
		}
		
		//若k比链表还长
		if(length<k){
			System.out.println("k="+k+"超过了链表长度!");
			result = false;
			return 0;
		}
		
		//遍历链表,遍历到第n-k个元素结束
		Node<Integer> q = first;
		for(int i=0;i<length-k;i++)
			q = q.next;
		
		return q.data;
	}
	
	/**
	 * 上述方法能解决问题,但需要遍历链表两次,能否有更高效的办法?
	 * 可以使用两个指针i和j,指针i从头开始先走k步,然后j指向第一个结点,接下来保持i和j之间的距离,当j走到尾时,i指向的结点就是倒数第k个结点。
	 * 代码如下:
	 */
	public static int getTailK_modify(Node<Integer> first,int k){
		//若链表为空
		if(first==null){
			System.out.println("链表为空!");
			result = false;
			return 0;
		}
		
		//若k<=0
		if(k<1){
			System.out.println("k不能小于1!");
			result = false;
			return 0;
		}
		
		//定义两个指针p和q,p指向头结点,q指向第k个结点
		Node<Integer> p = first;
		Node<Integer> q = first;
		//将q指向第k个结点
		for(int i=0;i<k-1;i++){
			//若q还没指向第k个结点,但q已经是最后一个结点,则说明k超过了链表长度
			if(q.next==null){
				System.out.println("k="+k+"超过了链表长度!");
				result = false;
				return 0;
			}
			q = q.next;
		}
		
		//p和q分别向后移动,直到q走到链表末尾为止
		while(q.next!=null){
			p = p.next;
			q = q.next;
		}
		
		return p.data;
	}
	
	
	
	/**
	 * 测试
	 */
	public static void main(String[] args){
		Node<Integer> node1 = new Node<Integer>();
		Node<Integer> node2 = new Node<Integer>();
		Node<Integer> node3 = new Node<Integer>();
		Node<Integer> node4 = new Node<Integer>();
		node1.data = 1;
		node2.data = 2;
		node3.data = 3;
		node4.data = 4;
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		System.out.println(getTailK_modify(node1,11));
	}
}

/**
 * 定义结点 
 */
class Node<T>{
	public T data;
	public Node<T> next;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P1341 无序字母对

题目描述 给定n个各不相同的无序字母对(区分大小写,无序即字母对中的两个字母可以位置颠倒)。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。...

36380
来自专栏Python爱好者

Java基础笔记17

16460
来自专栏Android机器圈

递归 —— 二分查找法 —— 归并排序

二分法就是把一个数组折半查找,再折半直到找到数据位置,或者无数据位置。比如说1-100,你选的值是23,那么范围写法就是(索引写法类似)

21440
来自专栏desperate633

LintCode 线段树系列问题(线段树的构造,线段树的构造||,线段树的查询,线段树的查询II,线段树的修改)线段树的构造线段树的构造 II线段树的查询线段树查询 II线段树的修改

线段树是一棵二叉树,他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数,并按照如下的方式赋值:

9430
来自专栏老马说编程

(45) 神奇的堆 / 计算机程序的思维逻辑

前面几节介绍了Java中的基本容器类,每个容器类背后都有一种数据结构,ArrayList是动态数组,LinkedList是链表,HashMap/HashSet是...

23790
来自专栏IT可乐

JDK1.8源码(八)——java.util.HashSet 类

  在上一篇博客,我们介绍了 Map 集合的一种典型实现  HashMap  ,在 JDK1.8 中,HashMap 是由 数组+链表+红黑树构成,相对于早期版...

12220
来自专栏F_Alex

数据结构与算法(二)-线性表之单链表顺序存储和链式存储

前言:前面已经介绍过数据结构和算法的基本概念,下面就开始总结一下数据结构中逻辑结构下的分支——线性结构线性表

19820
来自专栏desperate633

LintCode 主元素 III题目分析代码

给定一个整型数组,找到主元素,它在数组中的出现次数严格大于数组元素个数的1/k。 注意事项 数组中只有唯一的主元素

6510
来自专栏Java技术栈

Java集合从菜鸟到大神演变

先来看一张集合概况图,这里从上到下列举了几个最经常用的集合 ? 1、集合接口 java.util.Collection 是一个集合接口。它提供了对集合对象进行基...

44560
来自专栏JavaEdge

LinkedHashMap源码分析(基于Java8)概要示例代码节点构造函数增删查遍历

43550

扫码关注云+社区

领取腾讯云代金券