Part 2: LinkedList Related Algorithm Interview Questions(Reverse)

Also Check: Algorithms and System Design Interview Questions

How to reverse a linked list using recursion and iteration?
In the iteration approach we reverse linked list using 3 pointers in O(n) time, This is done by creating a new list by reversing direction, and subsequently inserting the element at the start of the list.

	public void reverseIteratively(Node head) {
	Node current = head;
	Node previous = null;
	Node forward = null;
	while(current.next != null){
	// Saving reference of next node, since we are changing current node
	forward = current.next;
	// Inserting node at start of new list
	current.next = previous;
	previous = current;
	// Advancing to next node
	current = forward;
	}
	head = current;
	head.next = previous;
	}

view raw ReverseLinkedList.java hosted with ❤ by GitHub

We can also reverse a singly linked list by using recursion. We will traverse the linked list until we find the tail, this tail  would be the new head for reversed linked list.

	private Node reverseRecursively(Node node){
	Node newHead;
	//corner case
	if((node.next == null))
	return node;
	newHead = reverseRecursively(node.next);
	//reverse the link
	node.next.next = node;
	node.next = null;
	return newHead;
	}

view raw ReverseLinkedListRecersive.java hosted with ❤ by GitHub

-K Himaanshu Shuklaa..