用Java反向链表的程序

Question

我已经编写了以下代码，其中方法rev(list,list)不起作用。请帮我确定出了什么问题。

import java.io.*;
public class list
{
    int d;
    list l;
    list()
    {
        d=0;
        l=null;
    }
    void create()throws IOException
    {
        int n;// store number of nodes
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter the first data");
        this.d=Integer.parseInt(br.readLine());
        System.out.println("Enter number of nodes to be made");
        n=Integer.parseInt(br.readLine());
        list temp;
        list ptr=this;
        for(int i=1;i<n;i++)
        {
            temp=new list();
            System.out.println("Enter the next data");
            temp.d=Integer.parseInt(br.readLine());
            temp.l=null;
            ptr.l=temp;
            temp=null;
            ptr=ptr.l;
        }
    }
    void delete(list lst, int n)
    {
        list ptr=lst;
        list ptr1=ptr;
        int c=1;
        while(c<n)
        {
            ptr1=ptr;
            ptr=ptr.l;
            c++;
        }
        ptr1.l=ptr.l;
        ptr.l=null;
        ptr=null;
        ptr1=null;
    }
    void insertmid(list lst,int x, int n)
    {
        list temp=new list();
        temp.d=x;
        temp.l=null;
        list ptr=lst;
        int c=1;
        while(c<n)
        {
            ptr=ptr.l;
            c++;
        }
        temp.l=ptr.l;
        ptr.l=temp;
    }
    void rev(list lst,list lst1)
    {
        lst1=null;
        list ptr=new list();
        while(lst!=null)
        {
            ptr =lst;
            lst=lst.l;
            ptr.l=lst1;
            lst1=ptr;
        }
    }

    void display()
    {
        list ptr=this;
        while(ptr!=null)
        {
            System.out.print(ptr.d+"t");
            ptr=ptr.l;
        }
        System.out.println();
    }
    public static void main(String args[])throws IOException
    {
        list l2=new list();
        list l3=new list();
        l2.create();
        l2.display();
        l2.insertmid(l2,14,2);
        l2.display();
        l2.delete(l2, 3);
        l2.display();
        l2.rev(l2,l3);
        l2.display();
    }
}

Answer 1

您应该做的第一件事是熟悉Java命名约定，因为这将使您的代码更干净、更容易理解。您当前的代码无法区分类、方法或变量。

其次，您似乎来自C++背景，不知道Java总是传递值

以下是你正在做的一件毫无意义的事情：

void rev(list lst,list lst1)
{
    lst1=null;  // this is pointless, essentially, you are using a passed argument as a local variable. 
    // ...

下面的代码实际上是等效的：

void rev(list lst)
{
    list lst1=null; //just create lst1 right here, don't need to pass it in as a parameter
    // ...

现在，我不会去清理你的整个代码，但我会给你一个反向链表的算法，你可以把它合并到你的程序中：

public Node reverseList(Node head) {
    Node newHead = null;        // New head of the reversed list
    Node prev, curr, next;      // Tracker pointers to previous, current and next node
    prev = null;
    curr = head;
    next = null;
    while(curr != null) {       // Iterate through the list
        next = curr.next;       // Remember the next node
        curr.next = prev;       // Point the current node to the previous
        prev = curr;            // Update the previous node tracker to the current node
        curr = next;            // Update the current node tracker to the next node
        if(next == null) {      // If we reached list end, store the new head
            newHead = prev;
        }
    }
    return newHead;
}

Answer 2

您可以使用Java Collection类尝试此操作：

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
class ReverseList {
List<Integer>list=new LinkedList<Integer>();
public void initializeList(){
    Scanner in=new Scanner(System.in);
    System.out.println("Enter number of nodes:");
    int no=Integer.parseInt(in.next());
    for(int i=0;i<no;i++){
        list.add(Integer.parseInt(in.next()));
    }
    in.close();
}
public void displayList(){
    System.out.println(list);
}
public void reverseList(){
    List<Integer>list2=new LinkedList<Integer>();
    for(int i=list.size()-1;i>=0;i--){
        list2.add(list.get(i));
    }
    this.list=list2;
}
public static void main(String[] args) {
    ReverseList rl1=new ReverseList();
    rl1.initializeList();
    rl1.displayList();
    rl1.reverseList();
    rl1.displayList();
}
}

Answer 3

请，请遵循标准命名约定。这样做将使您的代码更易于阅读。特别是，引用类型（类和接口）的名称应该以大写字母开头（例如List），而方法和实例变量的名称应该以小写字母开头。

以下是对你的非工作方法的一些评论：

void rev(list lst,list lst1)
{

如果您要立即丢弃传递的任何值，那么传递lst1是毫无意义的，就像您在这里所做的那样：

    lst1=null;

在这里初始化变量"ptr"也是毫无意义的，因为您对它所做的第一件事（在循环开始时）就是分配一个新值。事实上，在循环体内部声明它会更干净。

    list ptr=new list();

下面的循环看起来可能还可以，但考虑一下它离开lst最初引用的对象的状态。提示：lst1初始化为null。

    while(lst!=null)
    {
        ptr =lst;
        lst=lst.l;
        ptr.l=lst1;
        lst1=ptr;
    }

现在考虑Java只有传递值，所以从调用程序的角度来看，传递给这个方法的任何引用都不会改变。

}

如果你仍然没有看到它，那么考虑这个问题：哪个节点现在处于列表的顶端？

从更普遍的意义上讲，您有一点建模问题，因为list类试图执行双重任务，不仅表示整个列表，还表示该列表中的节点。这是可行的，它具有可能有用的属性，但它也具有可能引起麻烦的属性。例如，不能用类的实例来表示空列表。您也无法通过具有rev()签名的方法有效地反转由类实例表示的列表。

Answer 4

使用Java类命名约定我准备并重写了您的代码以按照您的要求工作：

import java.io.*;
public class List
{
    private Integer data;
    private List next;
    List(Integer data, List next){
        this.data = data;
        this.next = next;
    }
    List(){
        this(0);
    }
    List(Integer data) {
        this(data, null);
    }
    List(List list) {
        this(list.getData(), list.getNext());
    }
    public void setData(Integer data) {
        this.data = data;
    }
    public Integer getData() {
        return this.data;
    }
    public void setNext(List next) {
        this.next = next;
    }
    public List getNext() {
        return this.next;
    }
    private List getElementAt(Integer element) {
        List tmp = this;
        for(int i = 0; i < element; i++){
            if (tmp.getNext() == null) {  // preventing NPE
                return tmp;
            }
            tmp = tmp.getNext();
        }
        return tmp;
    }
    public void add_nodes()throws IOException {
        Integer number_of_nodes;// store number of nodes
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter number of nodes to add");
        number_of_nodes = Integer.parseInt(br.readLine());
        List ptr = this;
        for(int i = 1 ; i < number_of_nodes ; i++)
        {
            List temp = new List();
            System.out.println("Enter the next data");
            temp.setData(Integer.parseInt(br.readLine()));
            ptr.setNext(temp);
            ptr = ptr.getNext();
        }
    }
    /**
    * Function used to cut n-th element from list
    *
    * @param element - 0 means first element
    */
    public void delete(Integer element){
        List tmp = this.getElementAt(element);
        if (tmp.getNext() == null) {
            return;                // preventing NPE
        }
        tmp.setNext( tmp.getNext().getNext() ); //cutting
    }
    public void insertmid(Integer position, Integer data){
        List tmp = this.getElementAt(position);
        List element = new List(data, tmp.getNext());
        tmp.setNext(element);
    }
    public void rewind(){
        List tmp = this;
        List result = new List(this);
        result.setNext(null);
        while(tmp.getNext() != null) { 
            tmp = tmp.getNext();
            List current = new List(tmp);
            current.setNext(result);
            result = current;
        }
        this.setData(result.getData());
        this.setNext(result.getNext());
    }

    void display()
    {
        List tmp = this;
        while(tmp != null) {
            System.out.print( tmp.getData() + "t");
            tmp = tmp.getNext();
        }
        System.out.println();
    }
    public static void main(String args[])throws IOException
    {
        List list = new List();
        list.add_nodes();
        list.display();
        list.insertmid(4, 2);
        list.display();
        list.delete(3);
        list.display();
        list.rewind();
        list.display();
    }
}

Answer 5

我只编写了在列表末尾插入节点的代码。您可以添加一个新的方法（函数），在开始时添加一个节点，并根据您的要求从列表中删除一个节点。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Node{
private int data;
private Node next;
private Node prev;
Node(Node n){
    this.data=n.data;
    this.next=n.next;
    this.prev=n.prev;
}
Node(int data){
    this.data=data;
    this.next=null;
    this.prev=null;
}
public int getData() {return data;}
public void setData(int data) {this.data = data;}
public Node getNext() {return next;}
public void setNext(Node next) {this.next = next;}
public Node getPrev() {return prev;}
public void setPrev(Node prev) {this.prev = prev;}
}   
class MyLinkedList{
    private Node start;
    private Node end;

    public Node getStart() {
        return start;
    }

    public void setStart(Node start) {
        this.start = start;
    }

    public Node getEnd() {
        return end;
    }

    public void setEnd(Node end) {
        this.end = end;
    }

    public boolean isEmpty(){
        return start==null;
    }
    //data from arguments
    public void addNode(int data) throws NumberFormatException, IOException{
        Node n=new Node(data);
        if(isEmpty()){
            start=end=n;
        }else
            if(start==end){
                start.setNext(n);
                n.setPrev(start);
                end=n;
            }
        else{
            end.setNext(n);
            n.setPrev(end);
            end=n;
        }
    }

    public void reverse() throws NumberFormatException, IOException{
        MyLinkedList revList=new MyLinkedList();
        Node currNode=this.getEnd();
        do{
            revList.addNode(currNode.getData());
            currNode=currNode.getPrev();
        }while(currNode!=null);
        this.start=revList.getStart();
        this.end=revList.getEnd();
    }
    public void traverseFromStart(){
        Node n=start;
        do{
            System.out.print(n.getData()+"-->");
            n=n.getNext();
        }while(n!=null);
        System.out.println();
    }
    public void traverseFromEnd(){
        Node n=end;
        do{
            System.out.print(n.getData()+"-->");
            n=n.getPrev();
        }while(n!=null);
        System.out.println();
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        MyLinkedList list=new MyLinkedList();
        System.out.print("Enter No. of Nodes:");
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        int noOfNodes=Integer.parseInt(in.readLine());
        for(int i=0;i<noOfNodes;i++){
            System.out.print("Enter value of this node:");
            list.addNode(Integer.parseInt(in.readLine()));
        }

        list.traverseFromStart();
        list.traverseFromEnd();
        list.reverse();
        list.traverseFromStart();
        list.traverseFromEnd();
    }
}

Answer 6

为此，代码使用for each循环对列表中的元素进行迭代，并将每个元素连接到名为output的字符串变量的前面。循环结束后，代码打印出输出字符串。

    public static void reverseList(LinkedList<String> list) {
    String output = "";
    for (String element : list) {
        output = element + " " + output;
    }
    System.out.println(output);
}