12

这是一个任务。我必须创建一个循环链表并删除列表中的每三个数字。当我的程序到达列表的末尾时，它应该回到头部并继续该过程，直到只剩下一个数字。

我在网上和其他一些参考书上搜索过，但无法解决我的问题。我发现的大多数参考资料都说：

除了循环列表没有尽头之外，它们与常规列表完全相同

或（取自我的教科书）：

如果最后一个节点的后继节点是第一个，则单链表是循环链接的

但是这些并没有告诉如何去做。我也尝试过使用我在这个网站上找到的一些代码，但这并没有解决任何问题。

我可以创建一个列表（我不知道它是否是一个循环链表）并显示它，但是元素的顺序很奇怪：

  • 如果列表有 6 个数字，则列表将为 1、6、5、4、3、2。
  • 如果列表有 8 个数字，则列表将为 1,8,7,6,5,4,3,2。

如果没有正确的列表，我可以正确地进行删除。以下代码有什么问题：

public class LastNumberDemo {
    public static void main(String[] args) {
        LastNumberNode ll=new LastNumberNode();
        System.out.println("how long is the list: ");
        Scanner keyboard = new Scanner(System.in);
        int input = keyboard.nextInt();

        if(input<=0) {
            System.out.println("no number to creat list");
        }
        if(input==1) {
            System.out.println("The Last number is 1.");
        }
        else {
            String[] n=new String[input];
            for(int index=0; index<n.length; index++)
                n[index]=Integer.toString(index+1);
            for(String e:n)
                ll.add(e);
            System.out.print("The list contains: \n");
            ll.print();
            System.out.print("\nThe last number is: ");
            ll.remove();
            ll.print();
        }
    }
}

//The circular linked list class
class LastNumberNode{
    private class Node{
        String value;  
        Node next;     

        Node(String val, Node n){
            value = val;
            next = n;
        }

        Node(String val){
            value=val;
            next=null;
        }
    } //This brace was missing - Edd

    private Node first;

    public LastNumberNode(){
      first = null;
    }

    public boolean isEmpty(){        
       return first == null;
    }

    public int size(){
        int count = 0;
        Node p = first.next;   
        while (p != first){
            count ++;
            p = p.next;
        }
        return count;
    }

    public void add(String e) {
        Node p=new Node(e);
        if(first==null){
            first=p;
            first.next=first;
        }
        else{
            first.next=new Node(e,first.next);
        }
    }

    public void remove(){
        while(size()>0){
            Node target=first.next.next;   
            Node temp=first;               
            target=target.next;          
            last.next=temp;
            first=target;
        }
    }

    public void print(){
        Node ref=first;
        for(int index=-1; index<size();index++)
            System.out.print(ref.value+" ");
        ref=ref.next;
    }
} //Extra brace removed - Edd
4

2 回答 2

7

当您Node向列表中添加一个新节点时，您将新节点添加Node到第二个位置（first.next指向您新添加的节点），但是这个新添加的节点first作为其下一个节点，使列表的其余部分未被引用（因此被垃圾收集并销毁）。使用您的add方法，您的列表不可能包含除 0、1 或 2 之外Node的任何内容。Node在列表中间添加 new 有点奇怪；要么将其添加到前面（newnode.next = first; first = newnode; last.next = first;），要么保留对列表后面的引用（如其他人所建议的那样），然后将其添加到那里。

就个人而言，我会重组LastNumberNode该类，使其具有以下操作链表的方法：

  • private void addNode(Node node)
  • private void removeNode(Node node)
  • private Node findNode(Node nextNode)

如果您维护对列表中最后一个节点的引用，那么您的addNode(Node node)方法可能类似于以下内容：

if(isEmpty()) {
    first = node;
    last = node;
}
else {
    Node tail = last;
    tail.next = node;
    node.next = first;
    last = node;
}

removeNode(Node node)基于以下几点：

Node prevNode = findNode(node);

if(node == first) {
    first = node.next;
    last.next = first;
}
else if(node == last) {
    prevNode.next = first;
    last = prevNode;
}
else {
    prevNode.next = node.next;
}

Node如果我要实现这一点，我可能会使用这种方法将列表减少到一个：

public String reduceList() {
    Node curNode = first;
    while(first != last) {
        removeNode(curNode.getNext().getNext());
        curNode = curNode.getNext().getNext();
    }

    return first.getValue();
}

最后一点，我不会费心用序列号填充数组，然后遍历它以将元素添加到列表中。我会直接进行以下操作：

for(int i = 1; i <= input; i++) {
    linkedlist.add(new Integer(i).toString());
}
于 2012-09-11T15:35:14.510 回答
4

如果 first 已设置，您的add方法会直接在之后插入元素：first

first.next = new Node(e, first.next);

这导致观察到的行为。

您需要跟踪列表的最后一个元素并添加新元素，就last.next好像要将新元素附加到列表的末尾一样。一种方法是简单地将对最后一个元素的引用保存在列表类的成员变量中，另一种方法是遍历列表，直到找到链接到的节点，该节点first将是最后一个节点。

于 2012-09-09T12:05:40.313 回答