描述
输入一个链表,输出一个链表,该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。
如果该链表长度小于k,请返回一个长度为 0 的链表。
示例1
输入:{1,2,3,4,5},1
返回值:{5}
1.遍历两次,第一次记个数,第二次找倒数
package com.LeetCodeProblem.JZ;
import java.util.*;
public class JZ14 {
public ListNode FindKthToTail (ListNode pHead, int k) {
if(k<=0||pHead==null) return null;// if(k<=0||pHead.equal(null)) return null;不行
int count=0;
ListNode temp=pHead;
while (temp!=null){
count++;
temp=temp.next;
}
if(count<k) return null;
temp=pHead;
for (int i = 0; i < count - k; i++) {
temp=temp.next;
}
return temp;
}
public class ListNode {
int val;
ListNode next = null;
public ListNode(int val) {
this.val = val;
}
}
}
2.快慢指针
思路:
使用快慢指针
先让快指针走k个,然后快慢指针一起走
当快指针为null时,慢指针就为所求
如何判断k是否合法呢?
在快指针走k个后,如果k大于链表长度
就会在循环里为null,这时候就说明k太大而不合法
而当快指针走完后,循环结束
正好为null,则此时结果正好是pHead。
public ListNode FindKthToTail (ListNode pHead, int k) {
if(pHead == null || k <= 0) return null;
//slow为慢指针,p为快指针
ListNode p = pHead,slow = pHead;
for(int i = 0;i < k;i++){
//循环里p如果为null,说明k已经超出链表长度范围
if(p == null) return null;
p = p.next;
}
//p如果正好为null,则所求为倒数第链表长度个,为pHead
if(p == null) return pHead;
//快慢指针同时往右移
while(p != null){
p = p.next;
slow = slow.next;
}
return slow;
}