[数据结构与算法]链表反转 TypeScript

一、迭代法

借助pre变量与next变量，防止迭代过程中丢失链表

type LinkedNode = {
  num: number;
  next: LinkedNode;
};
function reverse(head: LinkedNode) {
  let pre: LinkedNode | null = null; // 借助pre变量指向上一个结点(对象)
  let next: LinkedNode | null = null; // 借助next变量指向下一个结点(对象)
  // 直到head为null结束循环，此时pre变量指向链表最后一个结点(对象)
  while (head) {
    next = head.next;
    head.next = pre;
    pre = head;
    head = next;
  }
  return pre;
}

二、递归法

借助函数保存指针变量，防止丢失链表

type LinkedNode = {
  num: number;
  next: LinkedNode;
}
function reverse(head: LinkedNode) {
  if (!head.next) return head; // 递归结束条件，即此时head变量指向链表最后一个结点(对象)
  const newHead = reverse(head.next); // newHead变量指向链表的最后一个结点(对象)
  // 当运行到此处时，head变量指向的结点(对象)的下一个结点(对象)的其后所有结点(对象)的next指向已经反转
  head.next.next = head;
  head.next = null;
  return newHead;
}