04
16

发表于 • • 被 843 人看爆

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:

输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
示例2:

输入：[1, 1, 1, 1, 2]
输出：[1, 2]
提示：

链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicate-node-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

  1. 使用两个while循环，一个指向一个固定的值比如m，另一个从m的下一个节点开始扫描，如果遇到和m相同的结点，直接过滤掉，
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        ListNode p = head;
        while(p != null){
            ListNode q = p;
            while(q.next != null){
                if(p.val == q.next.val){
                    q.next = q.next.next;
                }else{
                    q = q.next;
                }
            } 
            p = p.next;
        }
        return head;
    }
}

2.set集合去重，从链表的头开始遍历，如果在set集合中有出现重复的元素，我们直接过滤掉

public ListNode removeDuplicateNodes(ListNode head) {
        Set<Integer> set = new HashSet<>();
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            set.add(cur.val);
            if (set.contains(cur.next.val))
                cur.next = cur.next.next;
            else
                cur = cur.next;
        }
        return head;
    }
分享到：