Reverse a Linked List

iterative way

1       ->       2     ->     3    ->    null
head          next

1       <-       2     ->     3    ->    null
prev          head         next

1       <-       2     <-     3    ->    null
               prev          head         next

1       <-       2     <-     3        null
                             prev        head        

Node reverse(Node head) {
  if (head == null || head.next == null) {
    return head;
  }

  Node prev = null;
  while (head != null) {
    Node next = head.next;
    head.next = prev;
    prev = head;
    head = next;
  }
 
  return prev;
}

recursive way

1    ->     2      ->    3    -> null
head       next

1    ->     2      <-    3
head       next       newHead

null    <-    1     <-     2    <-     3
             head         next        newHead

Node reverse(Node head) {
  if (head == null || head.next == null) {
    return head;
  }

  Node newHead = reverse(head.next);
  head.next.next = head.next;
  head.next = null;

  return newHead;
}