L2-002 链表去重

对于链表去重的问题，一种常见的解决方法是使用哈希表。具体步骤如下：

1. 初始化一个哈希表或者集合，用于存储已经出现过的节点的值。
2. 遍历链表，对于每个节点，检查其值是否已经在哈希表中存在。
- 如果值不存在于哈希表中，则将该值添加到哈希表，并继续遍历下一个节点。
- 如果值存在于哈希表中，则删除当前节点，即将当前节点的前一个节点指向当前节点的下一个节点，跳过当前节点。
3. 遍历完链表后，即可得到去重后的链表。

这种方法的时间复杂度为 O(n)，其中 n 是链表的长度。以下是示例代码（使用Python语言实现）：

def remove_duplicates(head):
    if not head:
        return head
    
    visited = set()
    visited.add(head.val)
    
    curr = head
    while curr.next:
        if curr.next.val in visited:
            curr.next = curr.next.next
        else:
            visited.add(curr.next.val)
            curr = curr.next
    
    return head

注意：以上代码仅展示了一种可能的解法，具体实现方式可能因编程语言和具体问题而有所不同。

相关问题

l2-002 链表去重 (25 分)

### 回答1：
在单链表中，如何去除重复的元素？

方法1:
1. 创建一个空的哈希表
2. 遍历链表，对于每个遍历到的节点，将其值放入哈希表中
3. 如果哈希表中已经存在该值，则删除该节点

方法2:
1. 从头节点开始，遍历整个链表
2. 对于每个遍历到的节点，从该节点的下一个节点开始，查找与该节点值相同的节点
3. 如果找到相同节点，则删除该节点

注意，这两种方法都需要维护链表的头节点。

### 回答2：
题目描述

给定一个带有重复元素的单链表，删除链表中重复的元素，使得链表中所有元素都是唯一的。

注意：不保留原链表中重复出现的数字。

输入格式：

第一行一个整数 N，为链表的总节点数。即下面的链表中，的数量。

第二行为不超过 N 的正整数，是单链表的节点的值。

输出格式：

链表的输出格式为

N node1→node2→node3→...nodeN

其中N为链表中节点个数，nodei表示链表中第i个节点的值。

注意：

如果链表为空，输出 NULL 。

如果链表有多个头结点，请保留最后一个。例如，链表1→2→2→3→3→4，应该输出1→4。

样例输入：

5
1 2 2 3 4
样例输出：

4 1→2→3→4

解题思路

本题需要对一个链表进行去重操作，使得链表中的每个元素只出现一次。根据这个描述，我们可以思考一下如何进行去重操作。

首先，我们可以开一个 hash 表，记录每个出现过的元素。然后对于链表中的每个元素，我们都查看一下它是否已经出现过，如果已经出现过，那么我们就将其删掉。

需要注意的是，如果链表有多个头结点，我们应该只保留最后一个头结点。那么，我们就需要在找出所有重复元素的位置之后，再去掉多余的头结点。

需要注意的一点是，这里题中的链表是单链表，而不是双向链表。这意味着我们不能通过双向指针来删除节点。 因此，我们只能遍历链表来找出重复元素的位置，并将它们删除。

时间复杂度：极端情况下，所有元素都不相同，那么 hash 表中就会存储所有元素，时间复杂度为 $O(n)$。在 worst case 时，遍历所有元素取出重复元素，时间复杂度为 $O(n)$。综合起来，时间复杂度为 $O(n)$。空间复杂度为 $O(n)$。

### 回答3：
思路：

题目要求实现链表去重，那么我们可以使用哈希表来实现。具体思路如下：

1. 定义一个哈希表，记录链表中每个值出现的次数。

2. 遍历链表，如果当前节点值在哈希表中的值已经是1了，说明已经出现过了，那么将当前节点从链表中删除。

3. 如果当前节点值在哈希表中的值还不是1，说明还没有出现过，那么将当前节点的值在哈希表中的值标记为1。

4. 继续遍历链表，直到到达链表的末尾为止。

5. 返回处理好的链表。

代码实现如下：

#include <iostream>
#include <unordered_map>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* deleteDuplicates(ListNode* head) {
    if (!head) return nullptr;
    unordered_map<int, int> map;
    ListNode* cur = head;
    while (cur) {
        map[cur->val]++;
        cur = cur->next;
    }
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;
    ListNode* pre = dummy;
    cur = head;
    while (cur) {
        if (map[cur->val] > 1) {
            pre->next = cur->next;
            cur = cur->next;
        } else {
            pre = cur;
            cur = cur->next;
        }
    }
    return dummy->next;
}

int main() {
    // Test case: 1 -> 2 -> 2 -> 3 -> 3 -> 4
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(2);
    head->next->next->next = new ListNode(3);
    head->next->next->next->next = new ListNode(3);
    head->next->next->next->next->next = new ListNode(4);
    ListNode* result = deleteDuplicates(head);
    while (result) {
        cout << result->val << "->";
        result = result->next;
    }
    cout << "NULL" << endl;
    return 0;
}

复杂度分析：

时间复杂度：我们需要遍历整个链表来构建哈希表，时间复杂度为 O(n)，同时我们需要再次遍历链表来删除重复节点，时间复杂度为 O(n)，因此总的时间复杂度为 O(n)。

空间复杂度：我们需要一个哈希表来存储链表中每个节点的值，因此空间复杂度为 O(n)。

设有两个带附加头结点的单链表L1和L2，它们所有结点的值都不重复且按递增顺序链接。设有一个算法，合并两个单链表。要求新链表不另外开辟空间，使用两个链表原来的结点，并保持结点的链接顺序仍按值递增顺序排列并消除值重复的结点。不允许引入额外的空间复杂度，写测试程序测试算法的正确性

合并两个带附加头结点的单链表 L1 和 L2 的算法可以按照以下步骤操作：

1. 创建一个新的头结点，将其 next 指针指向 null，这个新头结点将作为合并后的链表。
2. 使用两个指针 p1 和 p2 分别初始化为 L1 和 L2 的头节点。
3. 当 p1 或 p2 任一指针为空时，将另一个指针所指向的链表剩余部分添加到新链表的末尾。
4. 如果 p1 和 p2 都非空，并且 p1 的值小于 p2 的值，则将 p1 的下一个节点（即 L1 中当前元素）连接到新链表，然后移动 p1 到 p1 的下一个节点。
5. 否则，如果 p2 的值小于或等于 p1 的值，则将 p2 的下一个节点连接到新链表，然后移动 p2 到 p2 的下一个节点。
6. 重复步骤 4 和 5 直到其中一个指针为空。

测试程序可以设计为：

def merge_sorted_lists(head1, head2):
    # 算法实现...
    pass

# 测试数据
head1 = create_linked_list([1, 3, 5, 7])
head2 = create_linked_list([2, 4, 6, 8, 9])

# 初始化新链表
new_head = merge_sorted_lists(head1, head2)

# 遍历新链表检查排序和去重是否正确
current = new_head
while current is not None:
    print(current.value)
    if current.next is not None and current.value == current.next.value:
        current.next = current.next.next  # 跳过重复值
    current = current.next

# 验证结果是否符合预期，例如 [1, 2, 3, 4, 5, 6, 7, 8, 9]

这里假设 `create_linked_list` 是创建一个有序链表的函数，`value` 是链表节点的数据字段。通过比较新链表中的元素值以及验证是否删除了重复项，我们可以确认算法的正确性。需要注意的是，实际实现中需要提供合并函数 `merge_sorted_lists` 的具体代码。