【学习打卡】第四天 数据结构和算法

链表 - 具体案例

一、删除链表中的节点【leetcode - 237】

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。

题目数据保证需要删除的节点 不是末尾节点 。

问题：
由于只给了被删除节点，无法获取上一个节点，所以无法采用常规的删除链表节点的方式。

思路：

1. 将下一个节点的内容复制到当前要删除的节点上
2. 将当前要删除的节点的next指向 下下个节点

function deleteNode(node) {
    node.val = node.next.val;
    node.next = node.next.next;
};

二、删除排序链表中的重复元素【leetcode - 83】

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例：

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

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

思路：

1. 如果第一个节点不存在，直接返回
2. 如果第一个节点存在，声明一个指针，默认指向第一个节点head
3. 将当前节点和下一个节点进行比较
4. 如果相同，需要删除下一个节点，把当前节点的next执行下下个节点；
   如果不相同，将指针指向下一个节点
5. 循环3、4，直到指针的next为null为止

function deleteDuplicates(head) {
  if (!head) {
    return head;
  }
  let p = head;
  while (p.next) {
    if (p.val === p.next.val) {
      p.next = p.next.next;
    } else {
      p = p.next;
    }
  }
  return head;
}

引申：
如果上述的链表没有排序应该怎么去重？

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

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

思路：

• 在原来的基础上增加一个集合，辅助链表去重

var deleteDuplicates = function(head) {
  if (!head) {
    return head;
  }
  let set = new Set([head.val]);
  let p = head;
  
  while (p.next) {
    if (set.has(p.next.val)) {
      p.next = p.next.next;
    } else {
      set.add(p.next.val);
      p = p.next;
    }
  }
  return head;
}

三、反转链表【leetcode - 206】

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

示例：

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

思路：

1. 创建双指针p1、p2；p1默认指向null，p2默认指向head
2. p2的next指向p1；然后双指针往后移
3. 重复步骤2，直到p2的指针为空结束

function reverseList(head) {
  let p1 = null;
  let p2 = head;

  while (p2) {
    const temp = p2.next;
    p2.next = p1;
    p1 = p2;
    p2 = temp;
  }
  return p1;
};