首页 » Java » 剑指offer--链表中倒数第k个结点-java

剑指offer--链表中倒数第k个结点-java

2015-10-06 16:40:06阅读(453)

题目描述:
输入一个链表,输出该链表中倒数第k个结点。(hint: 请务必使用链表。)

解题思路:

首先我们考虑到,用普通的思想,获取链表的长度,然后输出第length-k个元素的值,就是倒数第k个元素的值了。但是考虑到面试的技巧,这种方法还是不行的,但是做题时可以AC的。但是考虑的复杂点,如果时间复杂度为O(n)呢,一次扫描是不可能获取长度,又输出的。因此采取判断链表循环的思路,采用两个指针,第一个指针提前k-1步向下走,第二个指针再随着第一个指针一直走。知道第一个指针指向末尾,第二个指针的元素的值,便是我们所要求得的值。


具体Java实现代码如下:

import java.util.Scanner;


public class SolutionKth {
	
	public class ListNode {
	    int val;
	    ListNode next = null;

	    ListNode(int val) {
	        this.val = val;
	    }
	}
	
	//创建链表
	public ListNode CreateList(int[] array)
	{
		ListNode head=new ListNode(array[0]);
		head.next=null;
		ListNode p=head;
		for(int i=1;i<array.length;i++)
		{
			ListNode q=new ListNode(array[i]);
			q.next=null;
			p.next=q;
			p=q;
		}
		return head;
	}
	
	//打印链表中的元素
	public void Print(ListNode head)
	{
		ListNode p=head;
		while(p!=null)
		{
			System.out.print(p.val+" ");
			p=p.next;
		}
	}
	
	//寻找链表中的倒数第K个数
	public ListNode FindKthToTail(ListNode head,int k) 
	{
		if(k<=0)
			return null;
		if(head==null)
			return null;
		ListNode p=head;
		ListNode q=head;
		int i=1;
		while(p.next!=null)
		{
			if(i<k)
			{
				p=p.next;
				i++;
			}
			else
			{
				p=p.next;
				q=q.next;
			}
		}
		if(i<k)
			return null;
		return q;
		
    }
	
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
    	String input=sc.nextLine();
    	String[] inputlist=input.split(" ");
    	int[] array=new int[inputlist.length];
    	for(int i=0;i<inputlist.length;i++)
    	{
    		array[i]=Integer.parseInt(inputlist[i]);
    	}
    	SolutionKth sk=new SolutionKth();
    	ListNode head=sk.CreateList(array);
    	sk.Print(head);
    	ListNode result=sk.FindKthToTail(head, 2); //此处程序中将k设置为2了,可根据需要修改
    	System.out.print(result.val);
	}
}

输入:1 2 3 5 7 10

输出:7

版权声明:本文为博主原创文章,未经博主允许不得转载。

最新发布

CentOS专题

关于本站

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

小提示

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