203. 移除链表元素

题目链接：https://leetcode.cn/problems/remove-linked-list-elements/

解题思路

1. 递归

链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。这道题要求删除链表中所有节点值等于特定值的节点，可以用递归实现。

对于给定的链表，首先对除了头节点 head 以外的节点进行删除操作，然后判断 head 的节点值是否等于给定的 val。如果 head 的节点值等于 val，则 head 需要被删除，因此删除操作后的头节点为 head.next；如果 head 的节点值不等于 val，则 head 保留，因此删除操作后的头节点还是 head。上述过程是一个递归的过程。

递归的终止条件是 head 为空，此时直接返回 head。当 head 不为空时，递归地进行删除操作，然后判断 head 的节点值是否等于 val 并决定是否要删除 head。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function (head, val) {
  if (head === null) {
    return head;
  }
  head.next = removeElements(head.next, val);
  return head.val === val ? head.next : head;
};

2. 直接使用原来的链表来进行移除节点操作

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function (head, val) {
  // 删除头结点
  while (head != null && head.val == val) {
    // 注意这里不是if
    head = head.next; // 将头结点向后移动一位
  }

  // 删除非头结点
  let cur = head;
  while (cur != null && cur.next != null) {
    if (cur.next.val == val) {
      cur.next = cur.next.next;
    } else {
      cur = cur.next;
    }
  }
  return head;
};

3. 设置一个虚拟头结点在进行移除节点操作

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function (head, val) {
  const dummyHead = new ListNode(0, head); // 设置一个虚拟头结点, 并且将虚拟头结点指向head，这样方面后面做删除操作
  // 等价于 const dummyHead = new ListNode(0); dummyHead.next = head;

  let cur = dummyHead;
  while (cur.next) {
    if (cur.next.val === val) {
      cur.next = cur.next.next;
      continue;
    }
    cur = cur.next;
  }
  return dummyHead.next; // dummyHead.next 是新的头结点
};

206. 反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/

解题思路

1. 借助栈

借助栈的后入先出的顺序，可以将顺序列表逆序。不过这不是原地反转，当然题目也没有要求。

处理过程如下：

1）从头到尾遍历链表，将节点val依次放入栈
2）从栈中依次取出val，构造新节点，并连接节点

时间复杂度O(N)，空间复杂度O(N)。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  if (!head) {
    return null;
  }

  const stack = [];
  let node = head;
  while (node) {
    stack.push(node.val);
    node = node.next;
  }

  // 构造新节点
  const newHead = {
    val: stack.pop(),
    next: null,
  };

  // 连接节点
  node = newHead;

  while (stack.length) {
    node.next = {
      val: stack.pop(),
      next: null,
    };
    node = node.next;
  }

  return newHead;
};

2. 原地反转

“原地反转”的思路简单，但是实现起来有一些细节需要处理。链表类的原地操作，大部分都是细节上容易出错，导致死循环或者报错。

准备当前节点node，和node的前一个节点preNode。整体的思路如下：

1）保留当前节点的下一个节点
2）将当前节点的next指向前一节点preNode
3）更新preNode为当前节点，更新当前节点为第一步保留的下一节点
4）判断当前节点是否是最后节点，如果不是，回到第一步；如果是，进入最后一步
5）将当前节点的next指向前一节点preNode

时间复杂度是O(N)，空间复杂度是O(1)

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  if (!head) {
    return null;
  }

  let node = head;
  let preNode = null;

  while (node.next) {
    const nextNode = node.next;
    node.next = preNode;
    preNode = node;
    node = nextNode;
  }

  node.next = preNode;
  return node;
};

3. 双指针法

首先定义一个 cur 指针, 指向头结点, 再定义一个 pre 指针, 初始化为 null。
然后就要开始反转了, 首先要把 cur->next 节点用 tmp 指针保存一下, 也就是保存一下这个节点。
为什么要保存一下这个节点呢, 因为接下来要改变 cur->next 的指向了, 将 cur->next 指向 pre, 此时已经反转了第一个节点了。
接下来, 就是循环走如下代码逻辑了, 继续移动 pre 和 cur 指针。
最后, cur 指针已经指向了 null, 循环结束, 链表也反转完毕了。F 此时我们 return pre 指针就可以了, pre 指针就指向了新的头结点。

记录 curr 下一节点的位置 temp = curr.next;
curr.next = prev; // 反转节点间指针的方向
prev = curr; // 将 prev 指针向后移动一位
curr = temp; // 将 curr 指针向后移动一位

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let curr = head;
  let prev = null;

  while (curr) {
    const temp = curr.next; //  保存一下 cur的下一个节点, 因为接下来要改变cur->next
    curr.next = prev; // 翻转操作
    // 更新pre 和 cur指针
    prev = curr;
    curr = temp;
  }
  return prev;
};