ReverseLinkedList

ReverseLinkedList.java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
  
  
  // recursion
  public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }
    // head  p1  p2  p3
    // head  p3  p2  p1->null
    //       p3  p2  p1  head
    ListNode reversed = reverseList(head.next);
    ListNode tail = head.next;
    tail.next = head;
    head.next = null;
    return reversed;
  }
  
  
  // iteration
  public ListNode reverseList(ListNode head) {
    if (head == null) {
      return null;
    }
    //  null   a    b    c
    //  prev   p    temp
    //        prev  p
    //              prev p
    //                   prev p
    ListNode prev = null;
    ListNode p = head;
    while (p != null) {
      ListNode temp = p.next;
      p.next = prev;
      // update
      prev = p;
      p = temp;
    }
    return prev;
  }
  
}