链表反转并向反转链表插入新节点

Question

我正在学习DSA，我正在尝试实现链表的反向操作，但是显然我写的create方法在执行reversal后不起作用操作。

代码如下：

import java.util.*;

public class reverse {
    Scanner sc = new Scanner(System.in);

    static class Node {
        int data;
        Node next;

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

    Node head = null;
    Node tail = null;

    public void create() {
        System.out.println("Enter data");
        int value = sc.nextInt();
        Node newnode = new Node(value);
        if (head == null) {
            head = newnode;
            tail = newnode;
        } else {
            tail.next = newnode;
            tail = newnode;
        }
    }

    public void reversal() {
        Node prev = null;
        Node temp = head;
        Node nxt = null;
        while (temp != null) {
            nxt = temp.next;
            temp.next = prev;
            prev = temp;
            temp = nxt;
        }
        head = prev;
    }

    public void display() {
        Node temp = head;
        while (temp.next != null) {
            System.out.println(temp.data);
            temp = temp.next;
        }
        System.out.println(temp.data);
    }

    public static void main(String[] args) {
        int d = 0, a;
        Scanner sc = new Scanner(System.in);
        reverse obj = new reverse();
        do {
            System.out.println("1.Create\n2.Reverse\n3.Display");
            int choice = sc.nextInt();
            switch (choice) {
                case 1:
                    obj.create();
                    break;
                case 2:
                    obj.reversal2();
                    break;
                case 3:
                    obj.display();
                    break;
                default:
                    System.out.println("Enter a valid number!");
                    break;
            }
            System.out.println("1-Continue,0-Exit");
            a = sc.nextInt();
            if (a == 1) {
                d = 1;
            } else if (a != 1 && a != 0) {
                System.out.println("Enter a valid number");
            } else {
                System.out.println("Code Terminated!!");
                d = 0;
            }
        } while (d == 1 && d != 0);
    }
}

这是输出：

1.Create 
2.Reverse 
3.Display
1

Enter data
1

1-Continue,0-Exit
1

1.Create
2.Reverse
3.Display

1

Enter data
2

1-Continue,0-Exit
1

1.Create
2.Reverse
3.Display
1

Enter data
3

1-Continue,0-Exit
1

1.Create
2.Reverse
3.Display
2

1-Continue,0-Exit
1

1.Create
2.Reverse
3.Display
3

Numbers are:
3
2
1

1-Continue,0-Exit
1

反转链表后

1.Create
2.Reverse
3.Display
1

Enter data
4

1-Continue,0-Exit
1

1.Create
2.Reverse
3.Display
3

Numbers are:
3
4

1-Continue,0-Exit
0

我不知道哪里出了问题。

Answer 1

在您的 reversal 方法中，您应该保留 3 个临时节点：

一个迭代列表（正如您所做的那样）。
一个保持反向列表的头部。
一个在列表遍历的每次迭代中为反向列表创建一个新节点。

在每个循环中，反向列表的新节点应包含当前访问节点的信息，然后您可以将反向列表附加到该节点（因此最后创建的节点指向第一个访问的节点）和最终用创建的新节点更新了反向列表的头部。

错误解释

您在反转列表后无法添加任何其他元素的原因是您的 tail 节点未更新。事实上，在您的版本中，tail 仍然引用 non-existing 节点（一旦您使用新的反向列表更新 head，旧列表就会消失）。在您的 while 循环中，您需要将 tail 设置为创建的第一个新节点，因为这将成为循环结束时反向列表的最后一个节点，即您的尾巴。

public void reversal() {
    //Temp node to iterate the list
    Node temp = head;
    
    //Head of the reversed list
    Node headRev = null;
    
    //Temporary node to create at each iteration a new node for the reversed list
    Node newNode;

    //Resetting the tail
    tail = null;

    //Iterating the list
    while (temp != null) {
        
        //Creating a new node with the info of the current node
        newNode = new Node(temp.data);

        //Setting the tail of the new reversed list with the first node created
        tail = tail == null ? newNode : tail;
        
        //Appending to the new node the rest of the reversed list
        newNode.next = headRev;
        
        //Moving the head of the reversed list to the new node just created
        headRev = newNode;
        
        //Moving the iteration of the list to the next node
        temp = temp.next;
    }
    
    //Updating the head node of the list with the head of the reversed list
    head = headRev;
}

链表反转并向反转链表插入新节点

Linked List reversing and inserting new node to the reversed linked list

java

reverse

linked-list

data-structures

错误解释