Program to reverse a linked list
Category: Data Structures
Given a linked list, write a program to reverse elements of a linked list. e.g.- for linked list 1 -> 2 -> 3 -> 4 -> 5, output should be 5 -> 4 -> 3 -> 2 -> 1.
Problem-
Reverse elements of a linked list.
Solutions-
Solution 1 - (Iterative solution):
Program (Iterative)
Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insertAtEnd(self, data):
node = Node(data)
if self.head is None:
self.head = node
else:
temp = self.head
while temp.next:
temp = temp.next
temp.next = node
def traverse(self):
temp = self.head
while temp:
print(temp.data, end=' ')
temp = temp.next
print()
def reverse(self):
temp = self.head
prev = None
nextTemp = temp.next
while nextTemp:
temp.next = prev
prev = temp
temp = nextTemp
nextTemp = nextTemp.next
temp.next = prev
self.head = temp
linkedlist = LinkedList()
linkedlist.insertAtEnd(5)
linkedlist.insertAtEnd(1)
linkedlist.insertAtEnd(6)
linkedlist.insertAtEnd(8)
linkedlist.insertAtEnd(9)
print('Before reversing:')
linkedlist.traverse()
print('After reversing:')
linkedlist.reverse()
linkedlist.traverse()
Java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
LinkedList() {
head = null;
}
public void insertAtEnd(int data) {
if (head == null) {
head = new Node(data);
}
else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new Node(data);
}
}
public void traverse() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public void reverse() {
Node temp = head;
Node prev = null;
Node nextTemp = temp.next;
while(nextTemp != null) {
temp.next = prev;
prev = temp;
temp = nextTemp;
nextTemp = nextTemp.next;
}
temp.next = prev;
head = temp;
}
}
class Main {
public static void main(String[] args) {
LinkedList ll = new LinkedList();
ll.insertAtEnd(5);
ll.insertAtEnd(1);
ll.insertAtEnd(6);
ll.insertAtEnd(8);
ll.insertAtEnd(9);
System.out.println("Before reversing: ");
ll.traverse();
System.out.println("After reversing: ");
ll.reverse();
ll.traverse();
}
}
Output
Before reversing:
5 1 6 8 9
After reversing:
9 8 6 1 5
