reverse a single linked list - Java Snipplr Social Repository

Revision: 57196

at May 21, 2012 08:41 by edwarddr

Initial Code

class linkList 
{
    Node head;
	
	public linkList()
	{
		head = null;
	}
	
	
	
	public void reverse_all()
	{
		if (head == null || head._next == null)
			return;
			
		reverse_nc(head);
	}
 	
	// 1, 2, 3
	private Node reverse(Node n)
	{
		head = n;
		if (n._next == null) return head;
		
		Node nextNode = n._next;
		n._next = null;
		nextNode = reverse(nextNode);
		nextNode._next = n;
		return n;
	}
	
	// using non-recursion
	private void reverse_nc(Node n)
	{
		Node p = null;
		Node q = null;
			
		while (n != null){
			p = n._next;
			n._next = q;
			q = n;
			n = p;
			
		} 
		head = q;
	}
	
	
	void printV()
	{
		Node cur = head;
		while(cur!=null)
		{
			System.out.print(cur._value + " ");
			cur = cur._next;
		}
		System.out.println(", End!");
	}

	public static void main(String args[])
	{
		linkList list = new linkList();
		Node n1 = new Node(1);
		Node n2 = new Node(2);
		Node n3 = new Node(3);
		n1._next = n2;
		n2._next = n3;
		list.head = n1;
		
		list.printV();
		list.reverse_all();
		list.printV();
	}
}
class Node
{
	int _value;
	Node _next;
	
	Node( int value)
	{
		_value = value;
		_next = null;
	}
}

Initial URL

Initial Description

It's sample code of reversing a linked list with either recursive or non-recursive.

Initial Title

reverse a single linked list

Initial Tags

Initial Language

Java

Choose a language for easy browsing: