返回链接列表中的(2n/3)元素,同时在列表上循环一次

Question

我正在开发一个链表程序,它允许我只在列表上循环一次,而且我不能将列表的元素复制到另一个数据结构.

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

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

例如if n=1或n=2它返回第一个元素

if 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和tortoise跳跃for.此外,您必须null每次都进行检查,因为长度可能不是模3.