206. 反转链表

;(function () {
  /**
   * 206. 反转链表
   * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
   *
   * 输入：head = [1,2,3,4,5]
   * 输出：[5,4,3,2,1]
   *
   * 输入：head = [1,2]
   * 输出：输出：[2,1]
   *
   * 输入：head = []
   * 输出：[]
   *
   * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
   *
   */

  /**
   * Definition for singly-linked list.
   */
  class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
      this.val = val === undefined ? 0 : val
      this.next = next === undefined ? null : next
    }
  }
  function reverseList(head: ListNode | null): ListNode | null {
    // 方法一：双指针迭代 ? todo
    // 假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。
    // 在遍历链表时，将当前节点的 next 指针改为指向前一个节点。
    // 由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
    // let prev = null;
    // let curr = head;
    // while (curr) {
    //     const next = curr.next;
    //     curr.next = prev;
    //     prev = curr;
    //     curr = next;
    // }
    // return prev;

    // 方法二： 递归
    // 递归的两个条件：
    // ---- 终止条件是当前节点或者下一个节点==null
    // ---- 在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句： head.next.next = head
    let cur: ListNode | null = new ListNode(0)
    if (head === null || head.next === null) {
      return head
    }
    cur = reverseList(head.next)
    head.next.next = head
    head.next = null
    return cur
  }
})()