CODEWITHSUNDEEP
javanullpointerexceptionlinked-list
MMP
MMP

Reputation: 556

Practicing Singly Linked List implementation, stumped by my list reversal method throwing NullPointerException

Here is my singly linked list code:

public class SinglyLinkedList {

private static Node head;
private static int listSize;

private static class Node {

    int value;
    Node next;

    Node(int i) {
        value = i;
        next = null;
    }
}

public static void main(String[] args) {
    head = null;
    listSize = 0;
    for (int i = 0; i < 10; i++) {
        Node n = new Node(i);
        if (head == null) {
            head = n;
        } else {
            getLastNode(head).next = n;
        }
        listSize++;
    }
    printNodeValues(head);
    Node revHead = reverseList(head);
    printNodeValues(revHead);
}

private static Node reverseList(Node head) {
    Node reverseHead = getLastNode(head);
    Node reference = reverseHead;
    while (listSize>0){
        Node temp = getPreviousNode(reference, head);
        Node last = getLastNode(reverseHead);
        temp.next = null;
        last.next = temp;
        reference = temp;
        listSize--;
    }
    return reverseHead;
}

private static Node getPreviousNode(Node reference, Node head) {
    Node temp = head;
    while (temp != null) {
        if (temp.next == reference) {
            break;
        } else {
            temp = temp.next;
        }
    }
    return temp;
}

private static Node getLastNode(Node n) {
    Node temp = n;
    while (temp != null) {
        if (temp.next == null) {
            break;
        } else {
            temp = temp.next;
        }
    }
    return temp;
}

public static void printNodeValues(Node h) {
    while (h != null) {
        System.out.print(h.value + " ");
        h = h.next;
    }
    System.out.println();
}
}

The problem is with my reverseList(Node) method. When I run the program, I get the following error:

Exception in thread "main" java.lang.NullPointerException
at SinglyLinkedList.reverseList(SinglyLinkedList.java:44) -> temp = null;
at SinglyLinkedList.main(SinglyLinkedList.java:33) -> Node revHead = reverseList(head);

My printNodeValues works fine, and prints

0 1 2 3 4 5 6 7 8 9

and I'm trying to use reverseList to print

9 8 7 6 5 4 3 2 1 0.

Upvotes: 0

Views: 142

Answers (2)

Dici
Dici

Reputation: 25950

There are many very bad things in your code. Worst of all : why is everything static ? What's the point of writing a list class that can be instantiated only once ?

Then, the size of the list should never be affected by a reverse operation, and you don't even need a counter since you just have to iterate over the list until you find a node which has no successor.

private static Node reverseList(Node head) {
    Node res = null;    
    while (head != null) {
        Node node = new Node(head.value);
        node.next = res;
        res       = node;
        head      = head.next;
    }    
    return res;
}

Upvotes: 1

Ravi K Thapliyal
Ravi K Thapliyal

Reputation: 51711

Your reverseList() method needs to skip the iteration when it has reached the first node in the original list because it's previous node doesn't exist. This first node has already be assigned as the next node (i.e. the last node in the reversed list) in the second last iteration (of your original loop).

private static Node reverseList(Node head) {
    Node reverseHead = getLastNode(head);
    Node reference = reverseHead;

    int counter = listSize; 
    while ( counter > 1) {
        Node temp = getPreviousNode(reference, head);
        Node last = getLastNode(reverseHead);
        temp.next = null;
        last.next = temp;
        reference = temp;
        counter--;
    }
    return reverseHead;
}

Secondly, you shouldn't modify your listSize variable directly because the number of elements in the reversed list remains the same. Here, I'm storing it in a temporary counter first before iterating the list.

And, finally the reversed list should become your current head. Since, you've modified the linking between all the elements, it can only be traversed if your head now points to the new head.

printNodeValues(head);
head = reverseList(head);
printNodeValues(head);

Upvotes: 1

Related Questions