合并两个有序链表

  • 虚构头节点 + 指针

    /** * Definition for singly-linked list. * function ListNode(val, next) { *     this.val = (val===undefined ? 0 : val) *     this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} list1 * @param {ListNode} list2 * @return {ListNode} */var mergeTwoLists = function(list1, list2) {  const dummyHead = new ListNode(0, list1);  let current = dummyHead;  while(list1 !== null && list2 !== null) {    if(list1.val < list2.val) {      current.next = list1;      list1 = list1.next;    } else {      current.next = list2;      list2 = list2.next;    }    current = current.next;  }  current.next = list1 === null? list2 : list1;  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} list1 * @param {ListNode} list2 * @return {ListNode} */var mergeTwoLists = function(list1, list2) {    // 递归完结条件    if(list1 === null) return list2;    if(list2 === null) return list1;    if(list1.val < list2.val) {        list1.next = mergeTwoLists(list1.next, list2);        return list1;    } else {        list2.next = mergeTwoLists(list1, list2.next);        return list2;    }};

移除链表元素

  • 虚构头节点

    /** * 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);  let current = dummyHead;  while(current && current.next) {    // 只需找到要删除的节点的上一个节点    if(current.next.val === val) current.next = current.next.next;    else current = current.next;  }  return dummyHead.next;};

删除排序链表中的反复元素 II

  • 虚构头节点 + 循环判断相等

    /** * 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 deleteDuplicates = function(head) {    if(!(head && head.next)) return head;    const dummyHead = new ListNode(0, head);    let current = dummyHead;    while(current.next && current.next.next) {        if(current.next.val === current.next.next.val) {            const val = current.next.val;            while(current.next && current.next.val === val) {                current.next = current.next.next;            }        } else {            current = current.next;        }    }    return dummyHead.next;};
  • 哈希表 + 两次遍历