剑指offer:链表中倒数第k个节点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

首先想到的是从头结点开始遍历到链表的末尾，然后往前回溯k个节点，但是回溯？  这种方式只适用于双向链表，对于单向链表，是不可行的。

另外，如果我们已知了链表的长度，为n，那么倒数第k个节点，也就是从前往后的第n-k+1个节点，我们从前往后遍历n-k+1即可，然而我们并不知道链表的长度，所以需要先遍历一遍链表，才能取得它的长度，再遍历一边链表，才能输出第k个节点。所以这种方法的时间复杂度较高，需要遍历两遍才可以输出。

实现1：

public ListNode FindKthToTail(ListNode head,int k) {
        ListNode p=head;
        if(head==null||k==0){
            return null;
        }
        int length=1;
        while(head.next!=null){
            head=head.next;
            length++;
        }
        if(k>length){
            return null;
        }
        for (int i = 1; i <length-k+1; i++) {
            if(p.next!=null){
                p=p.next;
            }
            else{
                return null;   
            }  
        }
        return p;
 
    }

实现2：用堆栈的方式去实现

 public ListNode FindKthToTail(ListNode head,int k) {
        ListNode result=null;
		if(head==null||k==0){
			return null;
		}
		Stack<ListNode> s=new Stack<>();
		while(head!=null){
			s.push(head);
			head=head.next;
		}
		for (int i =1; i <= k; i++) {
			if(!s.isEmpty()){
				result=s.pop();
			}else{
				result=null;
			}			
		}
		return result;
    }

上面的这两种实现时间复杂度太高，并不是我们期望的结果。

如果想要只遍历一遍链表，就输出倒数的第k个元素，那么我们就需要两个指针。

（1）开始，让指针p1,p2都指向头结点，指针2先不动，指针1向前走k-1步；此时p1和p2之间相差k-1;

（2）从第k步开始，p1和p2同时移动，当p1指向链表的末尾时，此时p1所指的元素就是倒数第k个元素。

 

初步实现：

public ListNode FindKthToTail2(ListNode head,int k) {
        ListNode p1=head;
        ListNode p2=head;
        //第一个指针先走，直到遍历到链表的第k-1个节点
        for (int i = 1; i <=k-1; i++) {
            p1=p1.next;
        }
        //此时p1和p2之间相差k-1个元素，现在两个指针同时遍历
        while(p1.next!=null){
            p1=p1.next;
            p2=p2.next;
        }
        return p2;

    }

这个实现是有问题的，会报空指针异常，因为代码中存在多种特殊的情况没有被考虑到。

首先，如果给了一个空链表，那它的next是不存在的，此时会报错，

其次，如果给的k=0,则k-1=-1,也会报错；

另外，需要返回的k大于所给的链表的总长度时，也会报错，

考虑到以上情况，对代码做一些安全性的考虑，实现如下：

实现3：

 public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null||k==0){
            return null;
        }
        ListNode p1=head;
        ListNode p2=head;
        //第一个指针先走，直到遍历到链表的第k-1个节点
        for (int i = 1; i <=k-1; i++) {
            if(p1.next!=null){
                p1=p1.next;
            }
            else{
                return null;
            }
        }
        //此时p1和p2之间相差k-1个元素，现在两个指针同时遍历
        while(p1.next!=null){
            p1=p1.next;
            p2=p2.next;
        }
        return p2;
 

参考：

http://www.cnblogs.com/edisonchou/p/4769164.html