-1

以下是我查找双链表中间节点的代码，但它仅适用于奇数个节点。我不知道如何处理偶数节点的情况：

public Object findMiddleNode() {
    DLNode first = getHeadNode();
    DLNode last = getTailNode();
    while(first!=last) {
        first = first.getNext();
        last = last.getPrevious();
    }
    return first.getElement();      
}

这是我更新的代码：

public MyDequeue findMiddleNode() {
    DLNode first = getHeadNode();
    DLNode last = getTailNode();
    MyDequeue m = new MyDequeue();
    while(first!=last && first.getNext()!= last) {
        first = first.getNext();
        last = last.getPrevious();
    }
    if(first == last) {
        m.insertLast(first.getElement());           
        return m;
    }           
    else {
        m.insertLast(first.getElement());
        m.insertLast(last.getElement());
        return m;
    }
}

MyDequeue 类是我对双向链表的实现。我返回 MyDequeue 的原因是因为我已经有了一个打印双向链表元素的静态打印方法。

4

3 回答 3

1 
This is my code in java 
import java.util.LinkedList;

public class DeleteMiddleLinkedList {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<String>();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        list.add("5");

        DeleteMiddleLinkedList ds = new DeleteMiddleLinkedList();
        ds.middleDelete(list, "");

        for (String s : list) {
            System.out.println(s);
        }

    }

    public void middleDelete(LinkedList<String> list, String s) {
        int size = list.size();

        if (list == null) {
            return;
        }

        if (size % 2 == 0) {
            list.remove(size / 2);
            list.remove((size / 2) - 1);
        } else if (size % 2 != 0) {
            list.remove((size / 2));
        }

    }

}
于 2012-11-28T07:11:32.903 回答
1

对于偶数个节点，第一个和最后一个在中间相互通过。例如，如果您有 4 个节点 1..4，当 last 为 3 时，first 将为 2。在下一次迭代中，first 将为 3，last 将为 2。因此您永远不会失败 while 循环测试（first != last) 需要在适当的点退出循环。一个简单的解决方法是将您的 while 测试修改为

while ((first != last) && (first.getNext() != last)) {.

于 2012-09-11T20:55:37.017 回答
0

这是我更新的代码：

public MyDequeue findMiddleNode() 
{
    DLNode first = getHeadNode();
    DLNode last = getTailNode();
    MyDequeue m = new MyDequeue();
    while(first!=last && first.getNext()!= last) 
    {
        first = first.getNext();
        last = last.getPrevious();
    }
    if(first == last) 
    {
        m.insertLast(first.getElement());           
        return m;
    }           
    else 
    {
        m.insertLast(first.getElement());
        m.insertLast(last.getElement());
        return m;
    }
}

MyDequeue 类是我对双向链表的实现。我返回 MyDequeue 的原因是因为我已经有一个静态打印方法来打印双向链表的元素。对更好的解决方案有什么建议吗？

于 2012-09-12T04:38:01.497 回答