Road to Google – Part 8: Linked Lists

A linked list is a data structure in computer programming that is used to represent a sequence of elements, where each element points to the next one in the sequence. It is a dynamic data structure, meaning that its size can change during the execution of a program.

And there are two types of linked lists: Singular linked lists and Doubly linked lists.

This time around, we’ll only focus on Singular linked list.

Singular linked list

Doubly linked list

Each element in a linked list is called a node and it typically contains two parts:

1. Data: This is the actual value or information stored in the node.
2. Pointer: This is a reference to the next node in the sequence.

The first node in a linked list is called the head and the last node in the list is referred to as the tail. The tail node has a special value in its pointer, typically, indicating the end of the list.

The value can be anything, from an int-type number to a string.

And this is a pointer that is a reference to the next node in the sequence.

A pointer can be a reference either to the next node in the sequence or the end of it, namely null.

And a linked list has head and tail – usually, you get the head as an argument in a method to analyze the list.

And this is a cycled shape of a liked list.

And here comes our challenge.

Question:

Given a linked list, return it in reverse.

So, you get a linked list and return it in reverse – that’s what the question is asking for you to solve.

And if you get a single linked list that only contains an int-type value or Null, just return it as a final result.

How to solve:

When looking closer into the nodes 1,2 and null, in the reversed version, node 1 no longer points to node 2, and node 2 no longer points to node 3.

Let’s make a variable curr, which represents the current node, which is node 1 pointing at node 2. So, what we want to do is to make node 1 point at null instead of node 2.

If the pointer from node 1 to node 2 were to be severed, it would point to null, but we would also lose our connection to the next node from node 1. So we need another variable to keep track of the next node, which is curr.next. So we can safely update node 1’s pointer to null.

And if we update curr to node 2, we lose our connection to the previous node’s connection.

To solve the problem, we need another variable, called prev, to keep track of our previous node links. So we can safely update curr to the next node.

Then curr moves to node 2 and curre.next points to node 3.

Then, the pointer points at node 3 and curre.next points to node 4.

Then, the pointer points at node 3 and prev is updated to 2 -> 1 -> null, while the curr.next points at node 4.

Keep the cycle to node 4.

Update curr to node 5, and prev is updated to 4 -> 3 -> 2 -> 1 -> null, and curr.next points at the final null.

Finally, the loop ends here, and the method will return prev as the final result.

Coding solution:

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class ReverseLinkedList {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ReverseLinkedList solution = new ReverseLinkedList();
        ListNode reverseHead = solution.reverseList(head);

        System.out.println("Original List:");
        ListNode node = head;
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();

        System.out.println("Reversed List:");
        node = reverseHead;
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }
}

Step by step explanation:

The code starts by creating a ListNode class, which is used to represent each element in a linked list. Each element has a val field that stores its value, and a next field that stores a reference to the next element in the list.

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

The ReverseLinkedList class contains a reverseList method that takes a head parameter, which is a reference to the first element in the linked list.

Inside the reverseList method, we have two variables, prev and curr, which are initially set to null and head, respectively.

public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

The method then enters a while loop that continues as long as curr is not null. This means that the loop will continue until we reach the end of the linked list.

while (curr != null)

Inside the loop, we first store a reference to the next element in the list in a temporary variable called nextTemp. This is necessary because we will soon change the next field of the current element, and we want to remember where we need to go next.

ListNode nextTemp = curr.next;

Next, we change the direction of the next field of the current element, so that it points to the previous element instead of the next one. This is what actually reverses the direction of the linked list.

Since this one needs extra description, here it goes – the line curr.next = prev is used to reverse the direction of the pointers between the nodes in the linked list.

Initially, each node points to the next node in the list. However, to reverse the linked list, we need to change the direction of these pointers so that each node now points to the previous node instead. The curr.next = prev line is used to achieve this.

curr.next = prev;

We then move the prev and curr variables one step forward, so that prev becomes the current element and curr becomes the next element. This is the previously explained prev variable that keeps track of the reversed pointers’ history.

This one also needs extra description – the line prev = curr is used to move the prev reference to the current node, so that it is ready for the next iteration of the loop. In the next iteration, prev will be pointing to the node that was previously pointed to by cur, and curr will be updated to point to the next node in the list.

prev = curr;

The loop then continues from step 5, until we have reversed the direction of every element in the linked list.

curr = nextTemp;

Finally, the reverseList method returns the value of prev, which is now a reference to the last element in the reversed linked list.

return prev;

The main method creates a linked list with 5 elements, then calls the reverseList method to reverse the direction of the linked list.

The original linked list and the reversed linked list are then printed out to the console, so we can see the result.