java - 返回链表中的 (2n/3) 个元素，同时在链表上循环一次

Question

我正在开发一个链表程序，它允许我只循环列表一次，并且我无法将列表的元素复制到另一个数据结构。

假设列表不为空(至少有一个节点)并且最后一个节点的下一个节点为空。

以下方法返回长度为 n 的列表的索引 (2n/3) 处的元素。

例如，如果 n=1 或 n=2 则返回第一个元素

如果n=3或n=4则返回第二个元素。

我想保留一个临时节点，如果数字(2n/3)是整数，它就会获取下一个节点。 有更好的方法吗？

public class LinkedListNode {
    private int value;
    private LinkedListNode next;

    public LinkedListNode(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public LinkedListNode getNext() {
        return next;
    }

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

    public class ListUtils {

    public static LinkedListNode findTwoThirdsNode(LinkedListNode head){

        int length=0;
        LinkedListNode node=head.getNext();
        LinkedListNode tmp=head;
        double divresult=1;
        while (node!=null){
            length++;
            divresult=(2*length)/3;
            node=node.getNext();
            if (divresult%1==0){
                tmp=tmp.getNext();
            }

        }
        if (length==1 || length==2){
            return head;
        }
        else
            return tmp;

    }

}

Answer 1

您可以通过运行链接列表两次来实现此目的，但是交错(换句话说，无需重置)。您只需使用兔子和乌龟的方法:您让兔子每次迭代跳跃三次，而乌龟每次迭代跳跃两次:

LinkedListNode rabbit = head;
LinkedListNode tortoise = head;
while(rabbit != null) { //repeat until the rabit reaches the end of the list
    for(int i = 0; rabbit != null && i < 2; i++) {
        rabbit=rabbit.getNext(); //let the rabbit hop the first and second time
        if(rabbit != null) {
            tortoise=tortoise.getNext(); //let the tortoise hop the first and second time
        }
    }
    if(rabbit != null) {
        rabbit=rabbit.getNext(); //let the rabbit hop a third time
    }
}
return tortoise; //if reached the end, we return where the tortoise ended

如果您希望结果尽可能接近 2/3rd(因此不会有太多舍入误差)，您最好将 rabbit 和 交错乌龟 的跳跃与for 循环中的操作相同。此外，您每次都必须进行 null 检查，因为长度可能不是以 3 为模。