如何做一个反向链表

Question

问题是在倒排方法中，程序从不显示第一个数字。例如，如果要反转的数字是 1 2 3 4，则输出为3 2 1 0.没有 4，0 不应该在那里。请帮忙。

import java.util.Scanner;

public class LinkTest
{
    public static void main(String [] args)
    {
        ListNode head = new ListNode();
        ListNode tail = head;
        int x;
        head.link = null;
        Scanner keyboard = new Scanner(System.in);
        System.out.println("Enter a list of integers ending in zero.");
        x = keyboard.nextInt();
        while(x != 0)
        {
            ListNode newOne = new ListNode();
            newOne.data = x;
            newOne.link = null;
            tail.link = newOne;
            tail = newOne;
            x = keyboard.nextInt();
        }
            printLinked(head);
            delRep(head);
            invert(head);
    }
    public static void printLinked(ListNode cursor)
    {
        while(cursor.link != null)
    {
        System.out.print(cursor.link.data + " ");
        cursor = cursor.link;
    }
    System.out.println();
    }
    public static void delRep(ListNode num)
    {   
        ListNode current = num.link;
        ListNode cursor = null;
        ListNode duplicate = null;
    while(current != null && current.link != null)
    {
        cursor = current;
        while(cursor.link != null)
        {
            if(current.data == cursor.link.data)
            {
                duplicate = cursor.link;
                cursor.link = cursor.link.link;
            }
            else
            {
                cursor = cursor.link;
            }
        }
        current = current.link;
    }

    System.out.println("Here is the list without repeated ");
    printLinked(num);

    }
public static void invert(ListNode head)
{
    ListNode previous = null;
    ListNode current = head;
    ListNode forward;
    while (current != null) 
    {
        forward = current.link;
        current.link = previous;
        previous = current;
        current = forward;
    }
        System.out.println("Here is the inverted list.");
        printLinked(previous);
    }
}

Answer 1

您的问题是链表的head是一个虚拟的。对于输入 1 2 3 4，您可以创建以下内容：

0->1->2->3->4

打印时，跳过第一个节点。

但invert方法并没有把头部当作假人。它将列表还原为：

4->3->2->1->0

然后，由于打印方法跳过了头部，因此您将获得的输出是 3 2 1 0 .

这是修复：

public static void invert(ListNode head)
{
    ListNode previous = null;
    ListNode current = head.link;
    ListNode forward;
    while (current != null)
    {
        forward = current.link;
        current.link = previous;
        previous = current;
        current = forward;
    }
    System.out.println("Here is the inverted list.");
    head.link = previous;
    printLinked(head);
}