1. Reverse a linked list

1. Reverse a linked list

Problem link :- click here

package Linked_List;

public class LinkedList__1
{
	
	static void reverseListIterative(LinkedList list)
	{
		Node prev, cur, next;
		prev = null;
		cur = list.head;
		next = cur.next;
		
		while(cur != null)
		{
			next = cur.next;
			
			//update the link
			cur.next = prev;
			
			//now the update the nodes
			prev = cur;
			cur = next;
		}
		list.head = prev;
	}
	
	static Node reverseListRecursively(Node node)
	{
		if(node == null || node.next == null)
			return node;
		
		Node temp = reverseListRecursively(node.next);
		node.next.next = node;
		node.next = null;
		
		return temp;
	}
	
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		list.push(1);
		list.push(2);
		list.push(3);
		list.push(4);
		list.push(5);
		
		System.out.println("Given Linked list : ");
		printList(list);
		
		reverseListIterative(list);
		System.out.println("\nLinked list after reversing iteratively : ");
		printList(list);
		
		list.head = reverseListRecursively(list.head);
		System.out.println("\nLinked list after reversing recursively : ");
		printList(list);
	}

	static void printList(LinkedList list)
	{
		for(Node temp=list.head; temp!=null; temp=temp.next)
			System.out.print(temp.data + "-> ");
		System.out.println("null");
	}
}

Time complexity :- O(n)
Space complexity :- O(1)