链表中倒数第K个结点
考点:链表
题目描述
输入一个链表,输出该链表中倒数第K个结点
代码格式
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
}
}
解题一-直接输出结点的值
1.思路
由题中可以推断出:倒数第K个结点是正数第n-k+1个结点(n表示链表长度)。
如链表为1->2->3->4->5 当输出倒数第4个结点(即元素为2)时,正数(元素为2)为第5-4+1个结点。
[可行但不高效的常规解法:这种思路需要遍历链表两次,第一次统计出链表中结点的个数,第二次才能找到倒数第k个结点。]
2.代码如下
/*
public class ListNode {
int val;//存放数据的变量
ListNode next = null;//存放结点的变量,默认为null
ListNode(int val) { //构造方法
this.val = val;
}
}*/
public class Solution{
public ListNode FindKthToTail(ListNode head,int k) {
//定义链表的长度
int totalNum=0;
//判断head是否为空,为空则返回
if(head!=null){
totalNum++;
}else{
return null;
}
//计算总的结点数量
ListNode currentNode=head.next;
while(currentNode!=null){
totalNum++;
currentNode=currentNode.next;
}
if(totalNum < k){
//throw new RuntimeException("k的值超过了链表长度");
return null;
}
//倒数第k个为正数第totalNum-k+1个
ListNode resultNode = head;
for(int i=1;i<=totalNum-k;i++){
resultNode = resultNode.next;
}
return resultNode;
}
}
解题二-定义两个指针
1.思路
为了能够只遍历一次就能找到倒数第k个节点,可以定义两个指针:
(1)第一个指针从链表的头指针开始遍历向前走k-1,第二个指针保持不动;
(2)从第k步开始,第二个指针也开始从链表的头指针开始遍历;
(3)由于两个指针的距离保持在k-1,当第一个(走在前面的)指针到达链表的尾结点时,第二个指针(走在后面的)指针正好是倒数第k个结点。
下图展示了在有6个结点的链表上找倒数第3个结点的过程:
举一反三:当我们用一个指针遍历链表不能解决问题的时候,可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些(比如一次在链表上走两步),或者让它先在链表上走若干步。
2.代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null||k<=0)
{
return null;
}
//定义两个指针节点
ListNode pre=head;
ListNode last=head;
//先将一个节点往后移动k-1个距离
for(int i=1;i<k;i++)
{
if(pre.next!=null)
{
pre=pre.next;
}else
{
return null;
}
}
//一起移动
while(pre.next!=null)
{
pre=pre.next;
last=last.next;
}
return last;
}
}