Program to reverse a linked list


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.

linked list middle element

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

Recommended Posts