Author Topic: Java - Reverse Linked List  (Read 763 times)

kathir

  • Administrator
  • Sr. Member
  • *****
  • Posts: 283
Java - Reverse Linked List
« on: November 14, 2011, 03:22:04 pm »
Here is the complete source code for Java to reverse a singly linked list

Code:
//Source Code Listing


import java.lang.*;
import java.util.*;
import java.io.*;
 
class SLinkedList
{
   private int data;
   private SLinkedList next;
 
   public SLinkedList()
   {
      data = 0;
      next = null;
   }
 
   public SLinkedList(int value)
   {
      data = value;
      next = null;
   }
 
 
   public SLinkedList InsertNext(int value)
   {
      SLinkedList node = new SLinkedList(value);
      if(this.next == null)
      {
         // Easy to handle
         node.next = null; // already set in constructor
         this.next = node;
      }
      else
      {
         // Insert in the middle
         SLinkedList temp = this.next;
         node.next = temp;
         this.next = node;
       }
       return node;
   }
 
   public int DeleteNext()
   {
      if(next == null)
         return 0;
 
       SLinkedList node = this.next;
       this.next = this.next.next;  // can be NULL here
       node = null;
       return 1;
   }
 
   public void Traverse(SLinkedList node)
   {
      if(node == null)
         node = this;
      System.out.println("\n\nTraversing in Forward Direction\n\n");
 
      while(node != null)
      {
         System.out.println(node.data);
         node = node.next;
      }
   }
 
   public SLinkedList Reverse(SLinkedList head)
   {
      SLinkedList testnode = null;
      if(head == null)
            return head;
 
      while(true)
      {
            SLinkedList p = head;
            if(p.next == testnode)
                  break;
            while(true)
            {
                  int temp = p.data;
                  p.data = p.next.data;
                  p.next.data = temp;
                  p = p.next;
                  if(p.next == testnode)
                  {
                        testnode = p;
                        break;
                  }
            }
      }
      return head;
   }
 
   public SLinkedList Reverse_with_copy(SLinkedList head)
   {
      SLinkedList p = head;
      SLinkedList newhead = null;
      while(true)
      {
            if(p == null)
                  return newhead;
            SLinkedList newnode = new SLinkedList(p.data);
            newnode.next = newhead;
            newhead = newnode;
            p = p.next;
      }
   }
  
   public static void main(String[] args)
   {
      SLinkedList head = new SLinkedList(1);
      SLinkedList p = head.InsertNext(2);
      p = p.InsertNext(3);
      p = p.InsertNext(4);
      p = p.InsertNext(5);
      p = p.InsertNext(6);
      p = p.InsertNext(7);
      p = p.InsertNext(8);
 
      head.Traverse(null);
 
      SLinkedList newhead = head.Reverse(head);
      newhead.Traverse(null);
     
   }
}


output:

Traversing in Forward Direction
1
2
3
4
5
6
7
8
 
Traversing in Forward Direction
8
7
6
5
4
3
2
1

 


Disclaimer: This web site is for educational and informational purposes only. Click here to read the Disclaimer.
Content copyright 2010-2014. Kathiresan. All rights reserved.
This page is using SMF version 2.0.1