Advanced Search

reverse a single linked list

/ Published in: Java
Save to your folder(s)
It's sample code of reversing a linked list with either recursive or non-recursive.

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. class linkList 
  2. {
  3.     Node head;
  4.  
  5. 	public linkList()
  6. 	{
  7. 		head = null;
  8. 	}
  9.  
  10.  
  11.  
  12. 	public void reverse_all()
  13. 	{
  14. 		if (head == null || head._next == null)
  15. 			return;
  16.  
  17. 		reverse_nc(head);
  18. 	}
  19.  
  20. 	// 1, 2, 3
  21. 	private Node reverse(Node n)
  22. 	{
  23. 		head = n;
  24. 		if (n._next == null) return head;
  25.  
  26. 		Node nextNode = n._next;
  27. 		n._next = null;
  28. 		nextNode = reverse(nextNode);
  29. 		nextNode._next = n;
  30. 		return n;
  31. 	}
  32.  
  33. 	// using non-recursion
  34. 	private void reverse_nc(Node n)
  35. 	{
  36. 		Node p = null;
  37. 		Node q = null;
  38.  
  39. 		while (n != null){
  40. 			p = n._next;
  41. 			n._next = q;
  42. 			q = n;
  43. 			n = p;
  44.  
  45. 		} 
  46. 		head = q;
  47. 	}
  48.  
  49.  
  50. 	void printV()
  51. 	{
  52. 		Node cur = head;
  53. 		while(cur!=null)
  54. 		{
  55. 			System.out.print(cur._value + " ");
  56. 			cur = cur._next;
  57. 		}
  58. 		System.out.println(", End!");
  59. 	}
  60.  
  61. 	public static void main(String args[])
  62. 	{
  63. 		linkList list = new linkList();
  64. 		Node n1 = new Node(1);
  65. 		Node n2 = new Node(2);
  66. 		Node n3 = new Node(3);
  67. 		n1._next = n2;
  68. 		n2._next = n3;
  69. 		list.head = n1;
  70.  
  71. 		list.printV();
  72. 		list.reverse_all();
  73. 		list.printV();
  74. 	}
  75. }
  76. class Node
  77. {
  78. 	int _value;
  79. 	Node _next;
  80.  
  81. 	Node( int value)
  82. 	{
  83. 		_value = value;
  84. 		_next = null;
  85. 	}
  86. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.