Reverse a Linked List Java Program - The Coding Shala

Home >> Interview Questions >> Reverse a linked list

Reverse a Linked List

Reverse a Linked List Problem:

Reverse a singly linked list.

Example:

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

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



Reverse a Linked List Java Program


This problem can be solved by iteratively and recursively.

Approach 1: (Iterative Solution)
Take three Node prev, curr and next. Assign curr to prev and move ahead.

Java Code 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = null;
        
        while(curr != null){
            next = curr.next;
            curr.next = prev;
            
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

Approach 2: (Recursive)
Use recursion.

Java Code 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }
    
    ListNode reverse(ListNode head, ListNode newNode){
        if(head == null) return newNode; //linked list ends
        
        ListNode next = head.next;
        head.next = newNode;
        return reverse(next, head);
    }
}



Other Posts You May Like
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala