How to reverse a linked list in simple and optimal way in java

To reverse a linked list in Java, you can use an iterative approach which is both simple and optimal in terms of time complexity O(n) and space complexity O(1). Here’s how you can do it:

Iterative Approach:

• Initialize three pointers: previous, current, and next.
• Traverse through the list, reversing the direction of the next pointer for each node.

Here’s a step-by-step implementation:
`class ListNode {
int val;
ListNode next;

ListNode(int val) {
    this.val = val;
    this.next = null;
}

}

public class LinkedList {

// Function to reverse the linked list
public ListNode reverseList(ListNode head) {
    ListNode previous = null;
    ListNode current = head;
    ListNode next = null;

    while (current != null) {
        next = current.next;  // Store the next node
        current.next = previous;  // Reverse the current node's pointer
        previous = current;  // Move the previous pointer one step forward
        current = next;  // Move the current pointer one step forward
    }

    return previous;  // Previous will be the new head
}

// Function to print the linked list
public void printList(ListNode head) {
    ListNode temp = head;
    while (temp != null) {
        System.out.print(temp.val + " ");
        temp = temp.next;
    }
    System.out.println();
}

public static void main(String[] args) {
    LinkedList list = new LinkedList();

    // Creating the linked list: 1 -> 2 -> 3 -> 4 -> 5
    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);

    System.out.println("Original List:");
    list.printList(head);

    head = list.reverseList(head);

    System.out.println("Reversed List:");
    list.printList(head);
}

}`

Explanation:

1. ListNode Class:

• Represents a node in the linked list with an integer value and a pointer to the next node.

1. reverseList Method:

• previous: Keeps track of the previous node (starts as null).
• current: Keeps track of the current node (starts as head).
• next: Temporarily stores the next node.
• The while loop runs until current becomes null.
• Inside the loop:
• next stores the next node.
• The next pointer of the current node is reversed to point to previous.
• Move previous and current one step forward

This approach effectively reverses the linked list in linear time with constant space complexity.

✨ Enjoyed this post? If you found this content valuable, don’t forget to like to show your support! Your claps help others discover these insights.

🔔 Want to stay updated? Hit that follow button to never miss out on my latest posts and updates. Join our community and be part of the conversation!

Thanks for your support and engagement! 🙌