Reverse single linked list in java using non recursive algorithm (examples)

• Given a single linked list, we would like to reverse the single linked list.
• Reverse single linked list using non recursive or iterative algorithm in java.
•  Single linked list is shown in Fig 1, the head is located at node 1.
  • Each node in a linked list having reference to next node.

Algorithm – reverse single linked list in java (iterative algorithm)

1. head variable denotes head of single linked list.
2. Take couple of temporary variables
   • next = null
   • prev = null
3. next = head.next  (Step 1)
   • save reference of subsequent node in next variable
4. head.next = prev (node reversed) [Step 2]
5. prev = head (Step 3)
6. head = next (head points to second node) [Step 4]

Now apply the algorithm to reverse the linked list. Once we apply the above algorithm to complete linked list, we will get the reverse linked list as shown in Fig 3

Time complexity of algorithm is O(n).

Program – reverse single linked using non recursive algorithm in java.

1.) ReverseLinkedList Class:

• ReverseLinkedList class reverse the single linked list using non recursive algorithm.

package org.learn.Question;

import org.learn.List.Node;

public class ReverseList {
	public static Node reverseList(Node head) {
		Node next = null, prev = null;
		while (head != null) {
			next = head.next;
			head.next = prev;
			prev = head;
			head = next;
		}
		return prev;
	}

	public static void insert(Node head, int data) {
		while (head.next != null)
			head = head.next;
		head.next = new Node(data);
	}

	public static void print(Node head) {
		while (head != null) {
			System.out.printf("%d ", head.data);
			head = head.next;
		}
		System.out.println("");
	}
}

2.) App Class:

We are performing the following operation in this class

1. We are creating the single linked list in main method.
2. Print the single linked list before reversing single linked list.
3. Reverse the single linked list.
4. Print the reversed single linked list.

package org.learn.Client;

import org.learn.List.Node;
import org.learn.Question.ReverseList;

public class App {
	public static void main(String[] args) {
		int[] data = { 1, 2, 3, 4, 5 };
		Node head = new Node(data[0]);
		for (int count = 1; count < data.length; count++)
			ReverseList.insert(head, data[count]);
		System.out.println("Single linked list before reversal:");
		ReverseList.print(head);
		head = ReverseList.reverseList(head);
		System.out.println("Single linked list after reversal:");
		ReverseList.print(head);
	}
}

3.) Node Class:

• Node class representing the node(s) of single linked list

package org.learn.List;

public class Node {
	public int data;
	public Node next;

	public Node(int num) {
		this.data = num;
		this.next = null;
	}
}

Output – reverse single linked list using non recursive algorithm

Single linked list before reversal:
1 2 3 4 5
Single linked list after reversal:
5 4 3 2 1

Download code-reverse single linked list in java (non-recursive)