Contents

Reverse a linked list

Given a singly linked list, the task is to reverse the list. The head of the reversed list should be the last node of the original list, and the tail of the reversed list should be the first node of the original list.

Input-Output Examples

Example 1:

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

Example 2:

  • Input: 10 -> 20 -> 30 -> 40 -> NULL
  • Output: 40 -> 30 -> 20 -> 10 -> NULL

Example 3:

  • Input: NULL
  • Output: NULL

Approach:

To reverse a linked list, we need to change the next pointers of each node so that they point to the previous node instead of the next one. We can achieve this with a single pass through the list using three pointers.

Technique to be used: Iterative method using three pointers (prev, curr, next)

Steps to implement:

  1. Initialize three pointers: prev, curr, and next.
  2. Set prev to NULL and curr to the head of the list.
  3. Iterate through the list, updating next to curr->next, then setting curr->next to prev.
  4. Move prev to curr and curr to next.
  5. Repeat steps 3 and 4 until curr becomes NULL.
  6. Set the head of the list to prev.

C++ program to reverse a linked list

cpp
#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = NULL;
        ListNode* curr = head;
        ListNode* next = NULL;
        
        while (curr != NULL) {
            next = curr->next;  // Store the next node
            curr->next = prev;  // Reverse the current node's pointer
            prev = curr;        // Move pointers one position ahead
            curr = next;
        }
        return prev;  // New head of the reversed list
    }
};

// Helper function to print the linked list
void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
    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);

    Solution sol;
    head = sol.reverseList(head);

    // Printing the reversed linked list
    cout << "Reversed list: ";
    printList(head);

    return 0;
}

Java program to reverse a linked list

java
// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = null;
        
        while (curr != null) {
            next = curr.next;  // Store the next node
            curr.next = prev;  // Reverse the current node's pointer
            prev = curr;       // Move pointers one position ahead
            curr = next;
        }
        return prev;  // New head of the reversed list
    }
    
    // Helper function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        // Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
        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);

        Solution sol = new Solution();
        head = sol.reverseList(head);

        // Printing the reversed linked list
        System.out.print("Reversed list: ");
        printList(head);
    }
}

Python program to reverse a linked list

python
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        
        while curr:
            next = curr.next  # Store the next node
            curr.next = prev  # Reverse the current node's pointer
            prev = curr       # Move pointers one position ahead
            curr = next
        
        return prev  # New head of the reversed list

# Helper function to print the linked list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

# Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

sol = Solution()
head = sol.reverseList(head)

# Printing the reversed linked list
print("Reversed list:", end=" ")
print_list(head)

Reversing a linked list is a common problem that can be efficiently solved using the iterative method with three pointers (prev, curr, and next). This approach ensures a linear time complexity of O(n), where n is the number of nodes in the list.

DSA

Related Articles