Linked List: Program to reverse a linked list using iterative approach


Write a program to reverse a linked list using iterative method

Linked list is a series of nodes in which each node contains a data field and
reference (pointer) to the next node in the list. Using the reference pointer(next) between nodes, it forms a chain of nodes connected to each other.

 
Example

Imagine the following linked list that has 5 nodes:
20 -> 30 -> 60 -> 50 -> 10

 
Iterative Approach 
  1. Initialise three pointers say previous ,next and current
  2. Set the previous and current pointer as NULL.
  3. Also set the next pointer on the head node of linked list
  4. While next is not NULL perform following steps
    • previous = current
    • current = next
    • next = next.next
    • current.next = previous
  5. Now set the current pointer as the head node of the linked list
 
Complexity

Time Complexity : O(n) , where n is the size of linked list
Space Complexity : O(1)

 
Java Code
import java.util.*;

class ReverseLinkedListIterative{
	 class Node {
        // initialising data field and next pointer of node
        int data;
        Node next;
        Node(int data)
        {
            this.data = data;
            this.next = null;
        }
    }

    Node head;

    // insertion of node in linked list
    public void insert(int new_data) {
        Node temp = new Node(new_data);
        temp.next = head;
        head = temp;
    }
    public void printLinkedlist() {
        List allNodesList = new ArrayList<>();
        Node temp = head;
        while(temp != null)
        {
           allNodesList.add(Integer.toString(temp.data));
           temp = temp.next;
        }
        System.out.println(String.join(" -> ", allNodesList));
    }
 
    public void reverseIterative() {
        Node previous = null;
        Node current = null;
        Node next = head;
        while (next != null) {
            previous = current;
            current = next;
            next = next.next;
            current.next = previous;
        }
        head = current;
 
    }
    public static void main(String[] args) {
        // initialising object of linkedlist class
        ReverseLinkedListIterative ll = new ReverseLinkedListIterative();
        ll.insert(10);
        ll.insert(50);
        ll.insert(60);
        ll.insert(30);
        ll.insert(20);
 
        // call for iterative function
        System.out.println("Using Iterative Approach ");
        System.out.println("Original Linked List ");
        ll.printLinkedlist();
 
        System.out.println("Reversed Linked List ");
        ll.reverseIterative();
        ll.printLinkedlist();
        System.out.println();
 
     }
}
Output

Using Iterative Approach 
Original Linked List 
20 -> 30 -> 60 -> 50 -> 10
Reversed Linked List 
10 -> 50 -> 60 -> 30 -> 20



Thanks for feedback.



Read More....
Clone a Linked List
Find the middle of linked list with odd no of nodes
Check if linked list nodes form a palindrome
Delete a node at specific position from linked list
Delete a node from linked list
Detect if cycle is present in a linked list