反转 java 中的单向链表

Question

我在java中从头开始做了一个单向链表。代码如下：

public class SingleLinkedList<Item>
{
private Node head;
private int size;

private class Node
{
    Item data;
    Node next;

    public Node(Item data)
    {
        this.data = data;
        this.next = null;
    }

    public Node(Item data, Node next)
    {
        this.data = data;
        this.next = next;
    }
    //Getters and setters
    public Item getData()
    {
        return data;
    }
    public void setData(Item data)
    {
        this.data = data;
    }
    public Node getNext()
    {
        return next;
    }
    public void setNext(Node next)
    {
        this.next = next;
    }

}

public SingleLinkedList()
{
    head = new Node(null);
    size = 0;
}

public void add(Item data)
{
    Node temp = new Node(data);
    Node current = head;

    while(current.getNext() != null)
    {
        current = current.getNext();
    }

    current.setNext(temp);
    size++;
}

public void add(Item data, int index)
{
    Node temp = new Node(data);
    Node current = head;

    for(int i=0; i<index && current.getNext() != null; i++)
    {
        current = current.getNext();
    }

    temp.setNext(current.getNext());
    current.setNext(temp);
    size++;
}

public Item get(int index)
{
    if(index <= 0)
    {
        return null;
    }

    Node current = head;

    for(int i=1; i<index; i++)
    {
        if(current.getNext() == null)
        {
            return null;
        }

        current = current.getNext();
    }

    return current.getData();
}

public boolean remove(int index)
{
    if(index < 1 || index > size())
    {
        return false;
    }

    Node current = head;
    for(int i=1; i<index; i++)
    {
        if(current.getNext() == null)
        {
            return false;
        }

        current = current.getNext();
    }

    current.setNext(current.getNext().getNext());
    size--;
    return true;
}

public String toString()
{
    Node current = head.getNext();
    String output = "";
    while(current != null)
    {
        output+=current.getData().toString()+"  ";
        current = current.getNext();
    }

    return output;
}

public int size()
{
    return size;
}

public void reverse()
{
    Node current = head;
    Node prevNode = null;
    Node nextNode;

    while(current!=null)
    {
        nextNode = current.getNext();
        current.setNext(prevNode);
        prevNode = current;
        current = nextNode;
        System.out.println(prevNode.getData());
    }

    head = prevNode;

}

}

如你所见，我只在class中添加了反向功能。

但是当我尝试实际使用 class 时，在我尝试反转它后它给出了 NullPointerException。

为了检查功能，我使用了另一个名为 TEST 的 class。代码如下：

public class TEST
{

    public static void main(String[] args)
    {
        SingleLinkedList<Integer> list = new SingleLinkedList<Integer>();

        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        System.out.println(list.toString());

        list.reverse();
        System.out.println(list.toString());

    }
}

输出结果如下：

1  2  3  4  5  
null
1
2
3
4
5
Exception in thread "main" java.lang.NullPointerException
    at SingleLinkedList.toString(SingleLinkedList.java:129)
    at TEST.main(TEST.java:20)

我试图打印 prevNode 的值来检查它是否没有取值...但它是。怎么办？

Answer 1

 while(current!=null)

这是你的问题。当你点击最后一个节点时，你得到的 'next' 节点实际上是空的。

~~试试改成~~

~~while(current!=null&&current.getNext()!=null)~~

~~编辑：实际上不确定该解决方案是否有效。尝试在循环末尾放置一个条件语句：~~

~~if(current.getNext()==null) break;~~

编辑（再次 :/）：

好的，对不起，我没有想清楚。

将最终的 if 语句更改为：

if(current.getNext()==null){
    current.setNext(prevNode);
    break;
}

实际的空指针在 toString 中。这是您的操作：

将 while 条件更改为

while(current != null&&current.getData()!=null)

因为否则如果 current 指向 null 那么你会得到一个异常。

太累了。

Answer 2

实际上，你的反向方法看起来不错。

问题出在你的 toString() 方法上。
当您创建一个新列表时，您创建了一个初始元素，其数据为空。
您的 toString 方法会跳过第一个元素，因此只要您不反转列表，它就可以正常工作。
但是当您反转列表时，该空元素成为最后一个元素，并且当您在 current.getData() 为空时为最后一个元素调用 output+=current.getData().toString()+" "; 时，您会得到 NullPointerException.

您有多种选择：

您的反向方法可以先保留初始空元素（即反向列表的其余部分，但保持头部不变）。这样toString可以保持不变。
消除初始空元素。那么您的 toString 方法就不必跳过任何内容。

首先保留空元素：

public void reverse()
{
    Node current = head.getNext();
    Node prevNode = null;
    Node nextNode;

    while(current!=null)
    {
        nextNode = current.getNext();
        current.setNext(prevNode);
        prevNode = current;
        current = nextNode;
        System.out.println(prevNode.getData());
    }

    head.setNext(prevNode);

}

Answer 3

问题出在您的 SingleLinkedList.java toString() 方法

尝试下面它工作正常

    public String toString() {
        Node current = head;
        String output = "";
        while (current != null) {
//            output += current.getData().toString() + "  ";
            output += String.valueOf(current.getData()) + "  ";
            current = current.getNext();
        }

        return output;
    }

反转 java 中的单向链表

Reversing a singly linked list in java

java

linked-list

singly-linked-list