How to print the linkedlist from the middle node to the last node?-CodePudding

I'm trying to Solve a DSA problem on leetcode. I'm trying to run the code on vs code and trying to take the input list from the user and printing the Linked list from the middle node till the last node. I'm not able to print the desired linked list, instead my code prints the last element of the list. I've seen other answers related to linked list and all but still don't know what I'm doing wrong. Can you help me in solving this??

The problem is:- Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3.

Here's the solution:

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; }
}

Class to find the middle of the list and return the list node from the middle:

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;
    }
    
}

Main class:

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(); 
    }
}

CodePudding user response：

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(); 
    }
}

the problem is that when calling the new operation, ll will be resetted, and you only get the last node, see the comment in prevous code, the following code show one of the correct example.


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(); 
    }
}

CodePudding user response：

As mentioned in comments, your issue is that you pass ll into your middleNode method, but ll is referencing to your last node and your list is only one node long because you never make use of the next variable inside your loop, instead you replace the node entirely ll = new ListNode(sc.nextInt());.

The solution is quite simple, we need to keep two references when creating the linked list (I have renamed the variables so that they make more sense):

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

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

Then when we insert the next item we use previous.next = new ListNode NOT head = new ListNode(sc.nextInt());, note how we assign the next node using tail.next not head and not tail:

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

The complete working main method:

    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();

And the sample output from an input of 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