编码实现从无序链表中移除重复项(C和JAVA实例)

针对“编码实现从无序链表中移除重复项(C和JAVA实例)”，我来为你做一个详细的讲解攻略。

概述

无序链表中的元素可能会出现重复，我们需要从链表中移除这些重复项。本攻略将提供C语言和Java语言的实现示例，以帮助你更好理解链表去重的过程。

解题思路

链表去重的简单解法是使用哈希表。我们遍历链表中的每个节点，使用哈希表来存储这些节点包含的值。如果遇到一个节点其值已经在哈希表中存在，则将其从链表中删除。最终剩下的链表即为去重后的链表。

C语言实现

首先我们需要定义一个单向链表的数据结构。这里我们定义了一个结构体Node，表示链表的一个节点，其中val为节点的值，next为下一个节点的指针。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode {
    int val;
    struct ListNode *next;
};

接下来，我们定义一个removeDuplicates()函数，该函数实现了链表去重的功能。具体步骤如下：

1. 定义一个哈希表hash，用来存储链表中的节点。
2. 定义一个指针cur，初始指向链表头。
3. 定义一个指针prev，初始值为NULL，用于在链表中删除节点。
4. 遍历链表中的每一个节点，如果该节点的值已经在哈希表中存在，则将其从链表中删除；否则，将该节点的值存储在哈希表中。
5. 当前节点遍历完毕后，指针cur指向下一个节点，指针prev指向当前节点。
6. 重复步骤4和步骤5，直到遍历完整个链表。

struct ListNode* removeDuplicates(struct ListNode* head) {
    if (head == NULL) return head;

    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    struct ListNode* hash[100000] = {0}; // 哈希表

    while (cur != NULL) {
        if (hash[cur->val % 100000] != NULL) {
            // 删除重复节点
            prev->next = cur->next;
            free(cur);
        } else {
            hash[cur->val % 100000] = cur;
            prev = cur;
        }
        cur = prev->next;
    }

    return head;
}

Java实现

我们首先定义一个ListNode类，表示链表的一个节点，其中val为节点的值，next为下一个节点的指针。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

接下来，我们定义一个removeDuplicates()函数，该函数实现了链表去重的功能。具体步骤如下：

1. 定义一个哈希表hash，用来存储链表中的节点。
2. 定义一个指针cur，初始指向链表头。
3. 定义一个指针prev，初始值为null，用于在链表中删除节点。
4. 遍历链表中的每一个节点，如果该节点的值已经在哈希表中存在，则将其从链表中删除；否则，将该节点的值存储在哈希表中。
5. 当前节点遍历完毕后，指针cur指向下一个节点，指针prev指向当前节点。
6. 重复步骤4和步骤5，直到遍历完整个链表。

class Solution {
    public ListNode removeDuplicates(ListNode head) {
        if (head == null) return head;

        ListNode cur = head;
        ListNode prev = null;
        Map<Integer, ListNode> hash = new HashMap<Integer, ListNode>(); // 哈希表

        while (cur != null) {
            if (hash.containsKey(cur.val)) {
                // 删除重复节点
                prev.next = cur.next;
            } else {
                hash.put(cur.val, cur);
                prev = cur;
            }
            cur = prev.next;
        }

        return head;
    }
}

示例

这里给出两个示例：

1. 最简单的情况，链表中没有重复项。

// C语言实现
head: 1 -> 2 -> 3
removeDuplicates(head): 1 -> 2 -> 3

// Java实现
head: 1 -> 2 -> 3
removeDuplicates(head): 1 -> 2 -> 3

1. 链表中有重复项。

// C语言实现
head: 1 -> 2 -> 3 -> 2 -> 4 -> 3 -> 1 -> 5
removeDuplicates(head): 1 -> 2 -> 3 -> 4 -> 5

// Java实现
head: 1 -> 2 -> 3 -> 2 -> 4 -> 3 -> 1 -> 5
removeDuplicates(head): 1 -> 2 -> 3 -> 4 -> 5

以上就是编码实现从无序链表中移除重复项的详细攻略，希望可以对你有所帮助。

阅读剩余 65%