如何将LinkedList从中间节点打印到最后一个节点？

Question

我正在尝试解决leetcode问题 876。链接列表的中间：

给定单链接列表的头部，返回链接列表的中间节点。

如果有两个中间节点，请返回第二个中间节点节点。

输入： head = [1,2,3,4,5]
输出： [3,4,5]
说明：列表的中间节点是节点3。

我正在尝试在VS代码上运行我的代码，并尝试从用户获取输入列表，并从中间节点从中间节点打印链接列表最后一个节点。

我无法打印所需的链接列表，而是我的代码打印了列表的最后一个元素。我已经看到了与链接列表有关的其他答案，但所有的答案仍然不知道我在做什么错。您能帮我解决这个问题吗？

这是代码：

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

类：查找列表中间并从中间返回列表节点：

public class Solution {
    public ListNode middleNode(ListNode head) {
         ListNode slow=head, fast=head;
        while( fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;    
        }       
        return slow;
    }
}

主类：

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        ListNode ll= new ListNode();
        System.out.print("Enter the size of linked list: ");
        int size = sc.nextInt();
        System.out.println("Enter the elements of linked list: ");
        for(int i =1 ; i<=size ; i++){
            ll = new ListNode(sc.nextInt());
        }
        sc.close();
        Solution ob = new Solution();
        ListNode res=ob.middleNode(ll);
        System.out.println("Linked list starting from the: ");    
        while(res != null) {       
            System.out.print(res.val + " ");    
            res = res.next;    
        }    
        System.out.println(); 
    }
}

Answer 1

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        ListNode ll= new ListNode();
        System.out.print("Enter the size of linked list: ");
        int size = sc.nextInt();
         System.out.println("Enter the elements of linked list: ");
         for(int i =1 ; i<=size ; i++){
             // every time the new called, ll will be reseted.
             ll = new ListNode(sc.nextInt());
         }
        sc.close();
        Solution ob = new Solution();
        ListNode res=ob.middleNode(ll);
        System.out.println("Linked list starting from the: ");    
        while(res != null) {       
            System.out.print(res.val + " ");    
            res = res.next;    
        }    
        System.out.println(); 
    }
}

问题在于，在调用新操作时，LL将被重置，并且您只能获得最后一个节点，请参见Privous Code中的注释，以下代码显示了一个正确的示例之一。

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        ListNode ll = null, head = null;
        System.out.print("Enter the size of linked list: ");
        int size = sc.nextInt();
         System.out.println("Enter the elements of linked list: ");
         for(int i =1 ; i<=size ; i++){
             if (ll == null) {
               ll = new ListNode(sc.nextInt());
               head = ll;
             } else {
               ll.next = new ListNode(sc.nextInt())
               ll = ll.next;
            }
         }
        sc.close();
        Solution ob = new Solution();
        ListNode res=ob.middleNode(head);
        System.out.println("Linked list starting from the: ");    
        while(res != null) {       
            System.out.print(res.val + " ");    
            res = res.next;    
        }    
        System.out.println(); 
    }
}

Answer 2

如注释中所述，您的问题是您将ll传递到MiddleNode方法中，但是ll正在引用您的最后一个节点，而您的列表为只有一个节点长，因为您从不使用next在循环内的变量，而是完全替换了节点ll = new ListNode（sc.nextint（））;。

解决方案非常简单，在创建链接列表时，我们需要保留两个参考（我重命名了变量，以使它们更有意义）：

//The head of the list
ListNode head = new ListNode(0);

//The previous element or the tail of the loop
ListNode tail = head;

然后，当我们插入下一个项目时，我们使用PROVEN.NEXT.NEXT = new ListNode < /code> not head = new ListNode（sc.nextint（））;，请注意我们如何使用tail.next.next.next.next not head 而不是tail：

//insert the next node into the previous nodes next variable
tail.next = new ListNode(sc.nextInt());

完整的工作主方法：

    Scanner sc = new Scanner(System.in);
    //Keep a reference to the head
    ListNode head = new ListNode(0);
    //Keep a reference to the tail so we know where to insert the next node
    ListNode tail = head;
    //Create the list
    System.out.print("Enter the size of linked list: ");
    int size = sc.nextInt();
    System.out.println("Enter the elements of linked list: ");
    for(int i =1 ; i<=size ; i++){
        //Add the next node to tail.next
        tail.next = new ListNode(sc.nextInt());
        //Update the tail node to be the node that was just created
        tail = tail.next;
    }
    //Don't close System.in, this is a whole different issue, but don't do it.
    //sc.close();
    Solution ob = new Solution();
    ListNode res=ob.middleNode(head);
    System.out.println("Linked list starting from the: ");    
    while(res != null) {       
        System.out.print(res.val + " ");    
        res = res.next;    
    }    
    System.out.println();

以及1 2 3 4 5的输入的样本输出IS：

Enter the size of linked list: 5
Enter the elements of linked list: 
1 2 3 4 5
Linked list starting from the: 
3 4 5