206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
  1. Recursive
public ListNode reverseList(ListNode head) {
    if(head == null || head.next == null) return head;
    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}
  1. Iterative
public ListNode reverseListIterative(ListNode head) {
    ListNode sentinel = new ListNode(0), curr = head;
    sentinel.next = curr;
    while(curr != null && curr.next != null) {
        ListNode next = curr.next;
        curr.next = next.next;
        next.next = sentinel.next;
        sentinel.next = next;
    }
    return sentinel.next;
}