206. Reverse Linked List

Problem Statement

Reverse Linked List - LeetCode

Pattern: Related:Reverse LinkedList in Groups of K

---

Iterative Solution

public ListNode reverseList (ListNode head){
	ListNode prev = null, current = head; // next not init cuz head could be null
	while(current != null) {
		ListNode next = current.next;   // store the next ptr
		current.next = prev;            // flip curr nodes next to prev
		
		prev = current;                 // new prev is curr
		current = next;                 // new curr is next
	}
	return prev;
}

Recursive Solution

public ListNode reverse(ListNode head) {
	if(head == null || head.next == null) return head;  // return last node
	
	// GO DOWN
	ListNode last = reverse(head.next);  // goes to the last node
	
	// ON THE WAY UP
	head.next.next = head;                  // point the next node to myself
	
	head.next = null;                       // point myself to null
	
	return last;                         // return last NODE
}

Notes

• the ‘point myself to null’ line has any meaningful effect, only on the ‘first’ / ‘new last’ node.
• Basically
  • go down to the last node and keep returning it on the way back as the new head, no need to touch it.
  • on the way back point every node’s next to itself
• 👆 thats it. .thats the genius explanation