【每天一题】获取单向链表的倒数第K个元素

新浪微博 QQ空间 腾讯微博

思路:无论如何,如果不借助于辅助数据结构,那么链表的某些元素肯定需要被遍历两遍。
在使用辅助的数据结构的情况下,可以采用如下方案:
遍历的同时将每个节点的地址和序号记录在一个足够大的数组中,等到遍历完成时就可以从数组中找到倒数第K个元素。这肯定不是出题人的本意。
 
在对链表遍历两遍的情况下,可以有两种方案:
1、用两个指针,一个指针先走K步,然后第二个指针再从头开始,这样当地一个指针走到尾节点时,第二个指针的位置就是所需要的节点位置。
2、先遍历一遍链表得到链表的长度N,然后再从头遍历,直到第N-K个节点。
 
两种方法无优劣之分,但是前者显然更有“创意”,下面就方案1给出代码:

 
package get.lastk.element; 

public class Node
{
private int data;
private Node next;

private static int i = 0;

public Node(int data)
{
this.data = data;
System.out.println("The " + i++ + "th Node is " + data + ".");
}


public Node getNext()
{
return next;
}

public void setNext(Node next)
{
this.next = next;
}

public int getData()
{
return data;
}

public void setData(int data)
{
this.data = data;
}
}

package get.lastk.element;

import java.util.Random;

public class TestMain
{

public static void main(String[] args)
{
/*
* create a node list.
*/
final int bound = 2000;
Random random = new Random(System.currentTimeMillis());
Node listRoot = new Node(random.nextInt(bound));
Node next = new Node(random.nextInt(bound));
listRoot.setNext(next);
Node lastNode = null;
for (int i = 0; i != 18; i++)
{
lastNode = next;
next = new Node(random.nextInt(2000));
lastNode.setNext(next);
}

final int k = 50;
Node kthNode = getKthElementBackWords(listRoot, k);
if (kthNode != null)
{
System.out.println(kthNode.getData());
}
else
{
System.out.println("The " + k + "th node is null.");
}
}

public static Node getKthElementBackWords(final Node root, int k)
{
if (root == null || k <= 0)
{
return null;
}

Node firstNode = root;
Node secondNode = root;
while (--k >= 0 && firstNode != null)
{
firstNode = firstNode.getNext();
}

if (firstNode == null)
{
return null;
}

while (firstNode != null)
{
firstNode = firstNode.getNext();
secondNode = secondNode.getNext();
}
return secondNode;
}
}

未命名

新浪微博 QQ空间 腾讯微博

| 1 分2 分3 分4 分5 分 (4.88- 8票)
Loading ... Loading ... | 这篇文章归档在:Java, 算法数据结构
. | 永久链接:链接 | 评论(0) |

评论

邮箱地址不会被泄露, 标记为 * 的项目必填。

8 - 2 = *



You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <img alt="" src="" class=""> <pre class=""> <q cite=""> <s> <strike> <strong>

返回顶部