Problem Statement

Reverse a singly linked list.
Given a single linked list, reverse it in place.

Explanation

Given a linked list like below,

    1 -> 2 -> 3 -> 4 -> 5

We can use three pointers, to traverse through the list, keep one pointer on each node and reverse the chain. Majority of the linked list solutions use confusing pointer names which makes a very simple and intutive solution so difficult to understand.

Let 'curr' be the first pointer which points to head, we will also have 'prev' and 'next' which will be initially assigned to null.

    curr = head;
    prev = next = null;

We then assign curr's next to the 'next' pointer, 'prev' to the 'curr' next pointer.

    next = curr.next;
    curr.next = prev;

Now you just assign 'curr' to 'prev' and 'next' to 'curr'.

    prev = curr;
    curr = next;

Do this during the whole traversal in a loop and we are golden. Below is how the full code looks like.

public class ReverseLinkedList {
	
   class ListNode{
		int val;
		ListNode next;
		public ListNode(int val){
			this.val = val;
		}
	}

	public static void main(String[] args) {
		
		ListNode node = new ListNode(28);
		ListNode head = node;
		for(int i=5;i>0;i--){
			node.next = new ListNode(5*i);
			node = node.next;
		}
		printList(head);
		ListNode newHead = reverseLinkedList(head);
		System.out.println("After reversal");
		printList(newHead);

	}
	
	private static ListNode reverseLinkedList(ListNode head){
		ListNode next = null, prev = null, curr = head;
		while(curr!=null){
			next = curr.next;
			curr.next = prev;
			prev = curr;
			curr = next;
		}
		
		return prev;
	}
	
	private static void printList(ListNode node){
		ListNode temp = node;
		while(node!=null){
			System.out.println(node.val);
			node = node.next;
		}
	}

}

Time Complexity

We traverse through the whole list once and reverse the chain and so the time complexity is O(n), where n is the number of nodes.