1. Reverse Linked List

Solution 1: Iterative

1. In place operation, no extra space;

2. Shallow vs. deep copy

3. Stop condition: cur == null

TC: O(n)

SC: O(1)

class ListNode {
  int value;
  ListNode next;
  public ListNode(int value) {
    this.value = value;
    next = null;
  }
}

public ListNode reverse(ListNode head) {
  if (head == null) {
    return null;
  }
  ListNode cur = head;
  ListNode pre = null;
  ListNode nxt = null;
  while (cur != null) {
    nxt = cur.next;
    cur.next = pre;
    pre = cur;
    cur = nxt;
  }
  return pre;
}

Solution 2: Recursive

1. N1 -> N2 -> … Subproblem: N2 -> N3 -> ….

2. TODO: The head(N2) of subproblem points at cur(N1), cur(N1)'s next node is set to null.

N2: head.next

N2.next = N1 → head.next.next = head;

head.next = null; Make sure to avoid linked loop.

TC: O(n)

SC: O(n)

public ListNode reverse(ListNode head) {
  if (head == null) {
    return null;
  }
  ListNode newHead = reverse(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

Similarly, to reverse a linked list in pairs. Find out the subproblem.

e.g.

Input: N1-> N2 -> N3 -> N4 -> N5 -> null

cur next newHead

Output: N2 -> N1 -> N4 -> N3 -> N5 -> null

Solution:

1. Subproblem: N3->N4->...

2. N1->N4: cur.next points at the newHead of the subproblem

3. N2->N1: next becomes the head

public ListNode reverseInPairs(ListNode head) {
  if (head == null || head.next == null) {
    return head;
  }
  ListNode next = head.next;
  head.next = reverseInPairs(head.next.next);
  next.next = head;
  return next;
}