Java

java怎么删除单链表的重复节点

小亿
93
2023-12-15 02:55:56
栏目: 编程语言

可以使用两个指针来遍历单链表并删除重复节点。具体步骤如下:

  1. 定义两个指针,currnext,初始化时都指向链表的头节点。
  2. 使用一个HashSet保存已经出现过的节点的值,初始时为空。
  3. 遍历链表,当curr不为空时执行以下步骤:
    • 如果curr的值已经存在于HashSet中,说明当前节点是重复的,将next节点的值赋给curr节点,然后将next节点指向下一个节点。
    • 如果curr的值不存在于HashSet中,将curr的值添加到HashSet中,并将curr节点指向next节点,然后将next节点指向下一个节点。
  4. 返回链表的头节点。

下面是一个示例的Java代码实现:

public ListNode deleteDuplicates(ListNode head) {
    if (head == null) {
        return null;
    }

    ListNode curr = head;
    ListNode next = head.next;
    Set<Integer> set = new HashSet<>();

    set.add(curr.val);

    while (next != null) {
        if (set.contains(next.val)) {
            curr.val = next.val;
            curr.next = next.next;
        } else {
            set.add(next.val);
            curr = curr.next;
        }
        next = next.next;
    }

    return head;
}

请注意,此代码假设ListNode类的定义如下:

public class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

0
看了该问题的人还看了