Return 链表中第(2n/3)个元素在链表上循环一次

Question

我正在开发一个链表程序，它只允许我遍历列表一次，而且我不能将列表的元素复制到另一个数据结构。

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

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

例如，如果 n=1 或 n=2 它 return 是第一个元素

如果 n=3 或 n=4 它 return 是第二个元素。

我想保留一个临时节点，如果数字 (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

简单的 for 循环怎么样？

int n = // ...
int index = 2 * n / 3;
LinkedListNode current = head;
for(int i = 0 ; i < index ; ++i) {
    current = current.next();
}
return current;

Answer 2

你可以通过运行在链表上两次来做到这一点，但是 interleaved （换句话说没有重置).您只需使用 rabbit-and-tortoise-approach：兔子每次迭代跳 3 次，而 tortoise 每次迭代跳两次时间：

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 检查，因为长度可能不是模三。

Answer 3

保留 2 个指针，当你通过循环时，只有 2/3 的时间在它们的左边。

当你到达循环的末尾时return指向另一个节点的指针。

int i = 0;
node temp = head;
node progress = head;
while(progress != null) {
 i++;
 progress = progress.next;
 if(i == 2 && progress != null) temp = temp.next;
 else if ( i == 3 && progress != null) {
  temp=temp.next;
  i=0;
 }
}
return temp;
}

这是总体思路

Return 链表中第(2n/3)个元素在链表上循环一次

Return the (2n/3) element in a linked list while looping once on the list

java

oop

methods

linked-list

nodes