移除重复节点

面试题 02.01. 移除重复节点

题目要求：编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例

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

方法一：使用哈希表

利用哈希表记录已经出现的节点值，然后遍历链表，移除重复节点。

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var removeDuplicateNodes = function (head) {
    if (!head) return null;

    const seen = new Set();
    let current = head;
    seen.add(current.val);

    while (current.next) {
        if (seen.has(current.next.val)) {
            current.next = current.next.next;
        } else {
            seen.add(current.next.val);
            current = current.next;
        }
    }

    return head;
};

方法二：双重循环（不使用额外空间）

利用双重循环来检查每个节点是否有重复节点。时间复杂度较高，但节省空间。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var removeDuplicateNodes = function (head) {
    let current = head;

    while (current) {
        let runner = current;
        while (runner.next) {
            if (runner.next.val === current.val) {
                runner.next = runner.next.next;
            } else {
                runner = runner.next;
            }
        }
        current = current.next;
    }

    return head;
};

解释

  • 方法一：
    • 使用哈希表 seen 来记录已访问的节点值。
    • 遍历链表，对于每个节点，如果其值已经存在于 seen 中，则移除该节点；否则，将其值添加到 seen 中。
  • 方法二：
    • 对于每个节点，使用内部循环检查其后续节点中是否有重复节点。
    • 如果发现重复节点，则移除之；否则继续检查下一个节点。

选择使用哈希表的方法可以显著提高算法的效率，但需要额外的空间。

Last Updated:
Contributors: rosendo