Saturday, January 16, 2010

Java Program to reverse a Singly Linked List

Hi folks,

I have written an efficient way to reverse a Singly Linked List using three pointers/nodes for traversal/temporary purposes. I have given a pictorial representation of what happens with near, mid and far pointer. The program is mostly self explanatory. Remember, we are using our implementation of Singly Linked List. You may visit this link if you need that class.



Note : You may click on the above image to get a clearer picture.

Now, for the source code.
package dsa.linkedlist;

/**
 * Reverse a singly linked list
 * @author Braga
 */
public class ReverseAList {
 
 public static void main(String args[]){
  ReverseAList reverser = new ReverseAList();
  SinglyLinkedList<Integer> originalList = reverser.getLabRatList(10);
  System.out.println("Original List : "+originalList.toString());
  reverser.reverseList(originalList);
  System.out.println("Reversed List : "+originalList.toString());
 }
 
 public void reverseList(SinglyLinkedList<Integer> sourceList){
  if(sourceList.size<=1){
   return;
  }
  Node<Integer> nearNode = sourceList.start;
  Node<Integer> midNode, farNode;
  
  midNode = nearNode.next;
  farNode = midNode.next;
  
  nearNode.next = null;
  
  while(farNode!=null){
   midNode.next = nearNode;
   
   nearNode = midNode;
   midNode = farNode;
   farNode = farNode.next;
  }
  midNode.next = nearNode;
  sourceList.start = midNode;
 }
 
 private SinglyLinkedList<Integer> getLabRatList(int count){
  SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();
  for(int i=0;i<count;i++){
   sampleList.add(i);
  }
  return sampleList;
 }
}
//-----------------OUTPUT---------------------
//Original List : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
//Reversed List : 9, 8, 7, 6, 5, 4, 3, 2, 1, 0


Cheers,
Bragaadeesh.

21 comments:

HEMALATHA said...

HI
thanks a lot

Bragaadeesh said...

@Hemalatha : You're most welcome!

Eric said...

it's a clear explanation~
thanks~

i am a Java beginner, i want to ask what is:
dsa.linkedlist
??

i just find java.util.LinkedList at the Java API.

Bragaadeesh said...

@Eric: Thanks for reading my post!

Regarding your question dsa.linkedlist : Its a custom package name, nothing else. Yes, Java API is having a sophisticated LinkedList API, but its doubly linked list.
Purely for learning purpose, i want to write my own implementation for Singly Linked List and so I did. You can find the full class here.

Eric said...

I see~
Actually, I am learning the topic about the abstracted data type of java in this semester~
I really find your posts are helpful to my study~
Thanks a lot~

Bragaadeesh said...

Cool! Data structure is one of the coolest subjects and if you have passion and the thirst to learn it and gaining expertize in the process, you will find that you are well ahead in any competitive environment.

Eric said...

ha~
hope so~

afshia said...

thanks for your post.can u send me code to sort double circular header link list.please

Crazy as you can imagine said...

This is awesome!! You are so smart! I just get started learning Data Structure using Java, and find it really hard...But with your post, it is much clear!!! Just one last recommendation, it will be much better if you can explain how you come up with the solution!! Great work!!!This is going to be my primary learning blog! Thanks!

Bragaadeesh said...

@Crazy: Great to see that its beneficial.. Definitely will do proper explanations in future.

SV said...

Great articles. I always had difficulty implementing data structures using java, you articles walk me through ease.

Just a suggestion, where ever there are recursive algorithms you may also want to cover the iterative approaches for them... :)

Bragaadeesh said...

@SV: Thanks for stopping by!! I do have a recursive approach for this problem:). Check it out here : http://www.technicalypto.com/2010/03/reverse-singly-linked-list-recursively.html

SV said...

Impressed with your prompt response. Actually that comment was not relevant for this post ... but was meant for other posts like in BST search non recursive...

Also, it would be nice if you could cover Heap Sort and would be good to have table comaprison of the sorts mentioned in your article with time and memory complexity.

Fizi said...

I must say your implementations are very easy to understand so hats off to you. Thanks for all the hardwork. I plan on viewing every post on your site since its easy to understand than most code snippets on web

b said...

@Fizi : Thank you for reading !

Sim said...

Hi Bragaadeesh
Can you help me with something please.
I need to implement a basic singly-linked list tructure as a java class. it should allow adding and deleting of a element at specific position (maybe i) i very appreciate if you help me out

bragadeesh said...

@sim: yes there is. Check out the link I have provided in the content of this blog. Thanks for stopping by!

Mr .Techie said...

hey braga . " ur interview saver " ..some days before i had an interview for software programmer .. interviewer asked me same question's which i read in your blog ..thank god i knew the answer's ..thanks dude you r highly appreciated.keep doing the good work

BragBoy said...

@Mr.Techie,

Glad to hear it helped. Thanks for your comments !

Sudhasri said...

Is it a gud way to just swap the values in the node ,
(like first nodes value saps to the last node and so on..) instead of redirecting pointers?

BragBoy said...

Dear sudhasri,

yes, that would definitely do the trick. However the problem I have addressed is purely from an interview standpoint. If you are told that you should not swap values, then you will have to find a way to reverse the list. Hope you get the point.