首页 » Java » 剑指offer:链表中倒数第K个结点

剑指offer:链表中倒数第K个结点

原文 http://blog.csdn.net/wuxiaosi808/article/details/76709527

2017-08-05 12:20:07阅读(509)

题目:输入一个链表,输出该链表中倒数第k个结点

初看题目,感觉应该是从头到尾遍历链表,然后从尾回溯K步,因为是单向链表,此路不通。换条路吧。假设链表有n个结点,要找到倒数第K个结点,就是从头开始到第n-k+1个结点,但是n如何得到呢?需要从头到尾遍历,每遍历一个结点就count+1即可,这样需要遍历两次链表才能完成任务。如何才能遍历一次链表就能找到倒数第K个节点呢?

我们可以定义两个指针,第一个指针从头开始遍历到K-1个结点,第二个指针保存不动;从第K步开始,第二个指针也开始从链表头部遍历。由于两个指针的距离保持K-1不变,当第一个指针到尾部的时候,第二个指针正好到达倒数第K个结点。

代码如下:

要考虑是否是空链表,如果K==0,如果节点数小于K的三种情况。

}*/
import java.util.*;
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        
   
        if(head==null||k==0){  //空指针或者k==0的时候返回null
            return null;
        }
        ListNode p1=head;
        ListNode p2=null;
        for(int i=0;i<k-1;i++){
        if(p1.next!=null){
            p1=p1.next;
        }else{
            return null;  //如果节点数小于K,返回null;
        }
        }
        p2=head;
        while(p1.next!=null){
            p1=p1.next;
            p2=p2.next;
        }
        return p2;
    }
}



最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹