删除链表中重复的结点

1. 题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

2. 思路

遍历找出重复的节点存放到set中，然后在遍历判断是否在set中，是的话则删除

3. 实现

• java

public class 删除链表中重复的结点
{
    public ListNode deleteDuplication(ListNode pHead)
    {
        //检查参数
        if (pHead == null)
        {
            return null;
        }
        //遍历链表，如果当前节点与下一个节点相同，那么是重复的，加入set
        ListNode current = pHead;
        Set<Integer> set = new HashSet<>();
        while (current != null)
        {
            if (current.next != null && current.val == current.next.val)
            {
                set.add(current.val);
            }
            current = current.next;
        }
        //再次遍历链表，如果是在set中，那么删除之
        ListNode newHead = pHead;
        current = newHead;
        while (current != null)
        {
            if (current.next != null &&
                    set.contains(current.next.val))
            {
                current.next = current.next.next;
                continue;
            }
            current = current.next;
        }

        //头节点也可能重复
        if (set.contains(newHead.val))
        {
            newHead = newHead.next;
        }
        return newHead;
    }
}

• go

//空间：O（n）
//时间：O（n）
func deleteDuplication(pHead *ListNode) *ListNode {

	if pHead == nil {
		return nil
	}

	countMap := make(map[int]int)
	n := pHead
	for n != nil {
		countMap[n.Val] = countMap[n.Val] + 1
		n = n.Next
	}

	n = pHead.Next
	newHead := pHead
	newN := newHead
	for n != nil {
		if countMap[n.Val] == 1 {
			newN.Next = n
			newN = newN.Next
		}
		n = n.Next
	}

	newN.Next = nil
	if countMap[newHead.Val] > 1 {
		return newHead.Next
	}
	return newHead
}

func deleteDuplication(pHead *ListNode) *ListNode {
	if pHead == nil {
		return nil
	}

	count := make(map[int]int, 0)
	h := pHead
	for h != nil {
		count[h.Val]++
		h = h.Next
	}

	dummyHead := &ListNode{
		Val:  0,
		Next: pHead,
	}

	//删除使用两个指针
	prev := dummyHead
	current := prev.Next
	for current != nil {
		//下一个可能也是重复的，所以不需要更新prev
		if count[current.Val] > 1 {
			prev.Next = current.Next
		} else {
			prev = current
		}
		current = current.Next

	}

	return dummyHead.Next
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeDuplicateNodes(head *ListNode) *ListNode {
    m := make(map[int]bool, 0)
    dummyHead := &ListNode{}
    d := dummyHead
    current := head
    var next *ListNode
    for current != nil {
        //先保存下一个指针，后置空避免影响
        next = current.Next
        current.Next = nil
        if !m[current.Val] {
            d.Next = current
            d = d.Next
            m[current.Val] = true
        }
        current = next
    }
    return dummyHead.Next
}

4. 参考

• 删除链表中重复的结点_牛客网
• 面试题 02.01. 移除重复节点 - 力扣（LeetCode）
• 82. 删除排序链表中的重复元素 II - 力扣（LeetCode）