206.md

206. Reverse Linked List

Description

Reverse a singly linked list

Iterative approach

public ListNode reverseList(ListNode head){
  ListNode newNext = null;
  
  while(head != null){
    ListNode nextHead = head.next;
    head.next = newNext;
    newNext = head;
    head = nextHead;
  }
  //since head points to null when loop exits, newNext points to the last element of the original list
  return newNext;
}

Recursive approach

The following is my recursive approach

public ListNode reverseList(ListNode head) {
   return reverse(head, null);
}

ListNode reverse(ListNode head, ListNode lastHead){
    if(head == null)
        return lastHead;
    ListNode nextHead = head.next;
    head.next = lastHead;
    return reverse(nextHead, head);
}