Search code examples
javadata-structureslinked-listnodesreverse

How do I fix the following code so I get a reversed linked list for the output?


The following code is my attempt at implementing SinglyLinkedListNode and SinglyLinkedList classes and use the SinglyLinkedListNode reverse(SinglyLinkedListNode head) method to reverse this linked list.

The input consists of the first line detailing the number of test cases, t. And for each test case, the first line, n, represents the number of elements in the linked list. The next n number of lines will each contain an element from this list such that the input is as follows:

1 (number of test cases)
5 (number of elements in list)
1 (element in list)
2 (element in list)
3 (element in list)
4 (element in list)
5 (element in list)

How can I fix the following code so that it can print this reversed linked list, such that the output would be as follows:

5 4 3 2 1

As my code instead prints out the following:

1
5
1
2
3
4
5

1 2 3 4 5 

My code:

import java.util.Scanner;

public class ReverseLinkedList {

    static class SinglyLinkedListNode {
        public int data;
        public SinglyLinkedListNode next;

        public SinglyLinkedListNode(int nodeData) {
            data = nodeData;
            next = null;
        }
    }

    static class SinglyLinkedList {
        private SinglyLinkedListNode head;
        private SinglyLinkedListNode tail;

        public SinglyLinkedList() {
            SinglyLinkedListNode head = null;
            SinglyLinkedListNode tail = null;
        }

        public void insertNode(int nodeData) {
            SinglyLinkedListNode node = new SinglyLinkedListNode(nodeData);

            if (this.head == null) {
                this.head = node;
            } else {
                this.tail.next = node;
            }

            this.tail = node;
        }

        public SinglyLinkedListNode reverse(SinglyLinkedListNode head) {
            SinglyLinkedListNode previous = null;
            SinglyLinkedListNode current = head;
            SinglyLinkedListNode next = null;
            while (current != null) {
                next = current.next;
                current.next = previous;
                previous = current;
                current = next;
            }
            return previous;
        }

        public void printLinkedList() {
            SinglyLinkedListNode node = head;
            while (node != null) {
                System.out.print(node.data + " ");
                node = node.next;
            }
        }
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        SinglyLinkedList list = new SinglyLinkedList();

        int testCases = input.nextInt();

        if (testCases <= 10) {
            input.nextLine();
            int size = input.nextInt();
            if (size <= 1000) {
                for (int i = 0; i < size; i++) {
                    list.insertNode(input.nextInt());
                }
                list.reverse(list.tail);
                list.printLinkedList();
            }
        }
    }
}

Solution

  • use list.reverse(list.head)   
    

    and modify your reverse method as

     SinglyLinkedListNode previous = null; 
        SinglyLinkedListNode current = head; 
        SinglyLinkedListNode next = null; 
        while (current != null) { 
            next = current.next; 
            current.next = previous; 
            previous = current; 
            current = next; 
        } 
        head= previous; 
        return head;
    

    Also in your method printLinkedList set

          SinglyLinkedListNode node = tail; // instead of head