题目:
输入一个链表, 输出该链表中倒数第 k 个结点.
思路:
我们一先想到的应该是循环两次链表, 第一次获得它的长度, 然后用长度 - k, 得出目标节点在链表的第几位, 再循环一次.
如果要求只用一次循环的话, 我们就要借助两个指针, 第一个指针从立案表的头开始便利向前走 k-1 步, 第二个指针不动; 从 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) {
- if(head==null||k==0){
- return null;
- }
- ListNode pAhead = head;
- ListNode pBehind = null;
- for(int i=0;i<k-1;i++){
- if(pAhead.next!=null){
- pAhead = pAhead.next;
- }else{
- return null;
- }
- }
- pBehind = head;
- while(pAhead.next!=null){
- pAhead = pAhead.next;
- pBehind = pBehind.next;
- }
- return pBehind;
- }
- }
来源: http://www.bubuko.com/infodetail-2974874.html