Reverse a Linked List using Pointers | Leetcode 206

Reverse a Linked List using Pointers | Leetcode 206

LinkedList is one of the popular data structures that is used for collections. Though LinkedList isn't used as popularly as Arraylist, there are some advantages that linkedlist provides over ArrayList.  Firstly, if our list requires a lot of insertion or deletion in the middle then linkedlist performs better than arraylist.

Though you might not encounter any problems related to the linked list during an interview, there are some popular questions that are frequently asked in interviews. One such problem is reversing a linkedlist.

In this article, we will look at the popular leetcode problem of reversing a linkedlist.  First of all, let's understand what the problem is :

We strongly recommend you to give it a try on your own. You can find details about the problem through the link here:

Given the head of a singly linked list, reverse the list, 
and return the reversed list.

The first approach, we will use to reverse a LinkedList  by using Pointers.

Step one and Step two

To understand the problem easily, we are using the smallest linked list of length 2. First of all, we will be needing three-pointers to keep track of all the nodes while we are reversing.  We can name the pointers as a previous pointer, current pointer, and next pointer. We will start by pointing the previous pointer as null and our current pointer and next pointer will be pointing to the first node. We can then point the next Pointer to the second node and point the current pointer to the previous pointer. This way it will ensure that we have a track of all the nodes.

In step two, we will move the current pointer to point to the next pointer and repeat step 1 and step two again. We will repeat the steps unless our current pointer points to null.

Here is the solution for reversing a linkedlist problem.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode previousPointer = null;
        ListNode currentPointer = head;
        ListNode nextPointer = head;
        
        if(head == null || head.next == null) {
            return head;
        }
        
        while (currentPointer != null ) {
            nextPointer = nextPointer.next;
            currentPointer.next = previousPointer;
            previousPointer = currentPointer;
            currentPointer = nextPointer;
            
            
        }
        return previousPointer;
        
    }
}