链表中倒数第K个节点

问题描述

输入一个链表，输出该链表中倒数第K个节点。同时，从1开始计数，即链表的尾节点是倒数第一个节点。例如：一个链表有6个节点，从头节点开始，他们的值依次是1、2、3、4、5、6.这个链表的倒数第三个节点是值为4的结点

思路分析

首先想到的思路是，首先遍历该链表一次，就得到了该链表的长度，然后在遍历该链表一次，也就是倒数第k个节点就是顺数第总长度-k+1个位置的结点，但是从效率上说，遍历两次的时间复杂度为O（n*2);

码上有戏

public class RefindNum {

 
	
	public LinkNodes getReserve(LinkNodes head,int k){
		int count=1;
		LinkNodes node=head;
		if(node==null)
			return null;
		while(node.next!=null){
			count++;
			node=node.next;
		}
		int i=1;
		node=head;
		while(k<count&&i!=count-k+1){
			i++;
			node=node.next;
		}
		if(k<=count)
			return node;
		return null;
		
	}
	
	public static void main(String[] args) {
		RefindNum rf=new RefindNum();
		LinkNodes node1=new LinkNodes(1);
		LinkNodes node2=new LinkNodes(2);
		LinkNodes node3=new LinkNodes(3);
		LinkNodes node4=new LinkNodes(4);
		node1.next=node2;
		node2.next=node3;
		node3.next=node4;
		node4.next=null;
		System.out.println(rf.getReserve(node1, 2).data);
		

	}

}

class LinkNodes{
	int data;
	LinkNodes next;
	public LinkNodes(int data){
		this.data=data;
	}
}

两个指针解法

这种解法的思路，就是构造两个指针pre和behind，第一次使pre遍历到k-1位置，也就是第k个节点，此时在让behind指针从头开始遍历，由于pre和behind始终都相差k个位置，也就是说pre遍历到尾节点时，behind正好是倒数第k个节点，而此时的效率是很高的

码上有戏

public LinkNodes get(LinkNodes head,int k){
		LinkNodes pre=head;
		LinkNodes behind=null;
		if(pre==null||k<0)
			return null;
		for(int i=0;i<k-1;i++)
		{
			if(pre.next!=null)
				pre=pre.next;
			else
				return null;
		}
		behind=head;
		while(pre.next!=null)
		{
			pre=pre.next;
			behind=behind.next;
		}
		return behind;
	}