删除链表中的结点

  • 间接批改值和下一个节点

    /** * Definition for singly-linked list. * function ListNode(val) { *     this.val = val; *     this.next = null; * } *//** * @param {ListNode} node * @return {void} Do not return anything, modify node in-place instead. */var deleteNode = function(node) {    node.val = node.next.val;    node.next = node.next.next;};

删除链表的倒数第 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 * @param {number} n * @return {ListNode} */var removeNthFromEnd = function(head, n) {  const dummyHead = new ListNode(0, head);  let current = dummyHead;  let length = 0;  let index = 0;  while(current.next) {    length++;    current = current.next;  }  current = dummyHead;  while(length && current.next) {    if(length - index === n) {      current.next = current.next.next;      return dummyHead.next;    }    current = current.next;    index++;  }};

  • 虚构头节点 + 快慢指针

    /** * 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} n * @return {ListNode} */var removeNthFromEnd = function(head, n) {    const dummyHead = new ListNode(0, head);    // 别离定义 慢指针 和 快指针    // 慢指针 指向元素以及左侧元素个数 + 快指针 指向元素以及右侧元素个数 = 链表长度    let slow = dummyHead;    let fast = dummyHead;    // 将快指针挪动 n 位    for(let i = 0; i < n; i++) {        fast = fast.next;    }    // 将 快指针 挪动 链表长度 - n 位    // 此时 慢指针指向倒数第 n + 1 位    while(fast && fast.next) {        fast = fast.next;        slow = slow.next;    }    // 删除倒数第 n 位    slow.next = slow.next.next;    return dummyHead.next;};

反转链表

  • 双指针

    /** * 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 resultHead = null;  let currentOfHead = head;  while(currentOfHead) {    // 长期存储节点    const node = resultHead;    resultHead = currentOfHead;    // 因为此时 resultHead 与 currentOfHead 指向的是同一节点, 因而需先扭转 currentOfHead 指向    currentOfHead = currentOfHead.next;    resultHead.next = node;  }  return resultHead;};

  • 递归

    /** * 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 && head.next)) return head;    let newHead = reverseList(head.next);    head.next.next = head;    head.next = null;    return newHead;};

小结

  • 删除链表中的节点有两种形式:

    • 将 指标节点 的 上一节点 的 下一节点 指向 指标节点 的 下一节点, 如 pre.next = cur.next
    • 间接批改 以后节点 的 值 为 以后节点 的 下一节点 的值, 批改 以后节点的 下一节点 为 以后节点 的 下一节点 的 下一节点, 如 cur.val = cur.next.val; cur.next = cur.next.next

  • 删除倒数第 N 个节点有两种形式:

    • 记录长度并遍历
    • 应用双指针, 利用两指针之间的关系

  • 反转链表的两种形式:

    • 前插入节点
    • 递归