list - 寻找单链表的中间

Question

我已经修改了我的函数以处理偶数节点的情况，但因此我的代码不适用于奇数节点。怎么了？

public LinkedList findMiddleNode() {
    Node t1 = this.getHeadNode();
    Node t2 = this.getHeadNode();
    LinkedList l = new LinkedList();
    boolean even = false;
    while(t1.getNext() != null) {
        t1 = t1.getNext();
        if(t1.getNext()!= null && t1.getNext().getNext() != null) {
            t1 = t1.getNext();
            t2 = t2.getNext();              
        }
    }
    if(t1.getNext()!=null) 
        l.insertFirst(t2.getElement());
    else {
        l.insertFirst(t2.getElement());
        l.insertLast(t2.getNext().getElement());
    }
    return l;
}

Answer 1

@oldrinb：谢谢你的帮助，这是我更新的代码：

public LinkedList findMiddleNode() {
    Node t1 = this.getHeadNode();
    Node t2 = this.getHeadNode();
    LinkedList l = new LinkedList();
    boolean even = false;
    while(t1.getNext() != null && t1.getNext().getNext() != null) {
            t1 = t1.getNext().getNext();
            t2 = t2.getNext();              
    }
    if(t1.getNext()==null) 
        l.insertFirst(t2.getElement());
    else {
        l.insertFirst(t2.getElement());
        l.insertLast(t2.getNext().getElement());
    }
    return l;
}

Answer 2

/* determine length of list */
int n = 0;
for (Node cur = getHeadNode(); cur != null; cur = cur.getNext()) {
  ++n;
}

/* go half-way */
int m = n / 2;
Node mid = getHeadNode();
while (m > 0) {
  mid = mid.getNext();
  --m;
}

/* if n is odd, both mid and mid.getNext() are the middle */
if ((n % 2) != 0) {
  Node mid2 = mid.getNext();
  ...
} else {
  ...
}

...或者，或者，

Node tortoise = getHeadNode();
Node hare = getHeadNode();

do {
  tortoise = tortoise.getNext();
} while (hare.getNext() != null && (hare = hare.getNext().getNext()) != null);

/* tortoise is the middle */