【大厂算法题】反转链表

算法题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

输入：head = [1,2]
输出：[2,1]

循环解法

利用双指针循环遍历，直至链表的最后一个节点。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let prev = null;
  let curr = head;
  while (curr) {
    // nxt暂存下一个节点
    const nxt = curr.next;
    // 将当前节点的下一个节点改变，指向上一个节点
    curr.next = prev;
    // 当前的上一个节点变成curr，即往后移一个节点
    prev = curr;
    // 当前节点变成下一个节点，即往后移一个节点
    curr = nxt;
  }
  return prev;
};

递归解法

递归法的主要思想就是通过调用自身函数达到不断反转链表的指针和节点。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  // 判断头节点是否为空或者是否只有头节点
  if (head == null || head.next == null) {
    return head;
  }
  // 生成的新节点，递归调用
  const newHead = reverseList(head.next);
  // 将头节点的下一个指针指向头节点，也就是反转
  head.next.next = head;
  // 头节点的下一个指针指向null
  head.next = null;
  return newHead;
};