Linked List Pattern | Reverse Linked List |

3 min readNov 26, 2023

In our previous article I explained the concept of Merge Linked List, Two Pointer and also explained the thought process of some important problem on these concepts.

In this article, let’s learn another approach called reversing linked list and solve one problem in this article.

What is Reversing linked list?

As the name suggest, we are going to reverse the linked list.

Where to Use?

👊When you are asked to reverse the linked list.

👊When you are asked to reverse certain nodes.

👊When you are asked to check whether the given list is a palindrome or not.

👊When you are asked to reorder the list.

How to do?

Now we know what we are doing in this approach and when to use this approach. Let’s now learn how to reverse the linked list with help of the simple leetcode problem.

QNS Link: https://leetcode.com/problems/reverse-linked-list/description/

In this problem they asked us to reverse the list. These are like implementation problem i.e you can solve this at ease when you draw what is given and the desired output.

Let’s take the example which is given in leetcode,

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Input: 1 -> 2 -> 3 -> 4 -> 5-> NULL

Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULL

Use three pointers while reversing, they are previous pointer which points the previous node and current pointer which points to the current node and next pointer points to the next node to the current node. Initially they are,

previous = NULL
current=first node(head)
next=node next to the head node

In the above image I traced what happens in each iteration, how the previous, current(present) and the next pointer change during iteration. And I also mentioned when the iteration need to be stopped and what we have to return at the end. So go through the above image with patience to get the basic thought process of reversing.

The below is the complete solution for this problem. Please use pen and paper to get things clear.

In C:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head){
   struct ListNode* head1=NULL;
   struct ListNode* temp=head;
   struct ListNode* nxt=NULL;
   while(temp!=0){
       nxt=temp->next;
       temp->next=head1;
       head1=temp;
       temp=nxt;
   }
   return head1;
}

In Java:

/**
 * Definition for singly-linked list.
 * 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 Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode prev=null;
        ListNode present=head;
        ListNode next=present.next;
        
        while(present!=null){
            
            present.next=prev;
            prev=present;
            present=next;
            if(next!=null){
            next=next.next;}
        }
        return prev;

    }
}

Try the above program and get to understand about the flow using the debug pointers.

Let’s solve another problem where we use this approach which is a famous and frequently asked problem in big tech companies in my next article.

If you find any value in this article, consider FOLLOWING me! Thanks 😇

#LearnInPublic #HappyCoding

Linked List Pattern | Reverse Linked List |

Written by HolySpirit