输入一个链表,输出一个链表,该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。
如果该链表长度小于k,请返回一个长度为 0 的链表。
输入:{1,2,3,4,5},1
返回值:{5}
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; } } }
使用快慢指针
先让快指针走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; }