golang刷leetcode 链表(2) 删除重复元素
golang刷leetcode 链表(2) 删除重复元素
golangLeetcode
发布于 2022-08-02 15:55:51
发布于 2022-08-02 15:55:51
文章被收录于专栏：golang算法架构leetcode技术php
一、删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2示例 2:
输入: 1->1->2->3->3
输出: 1->2->3解题思路：由于是排序链表，所以，直接按照遍历的思路就可以解
1，如果cur.Val==next.Val,cur.Next=next.Next
2,链表正常遍历就行了
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates(head *ListNode) *ListNode {
cur:=head
if cur==nil{
return cur
}
next:=cur.Next
for next !=nil{
fmt.Println(cur,next)
if cur.Val==next.Val{
next=next.Next
cur.Next=next
fmt.Println(cur,next)
}else{
cur=next
next=next.Next
}
}
return head
}二、删除链表中重复元素（没有排序）
给定一个无序链表，删除所有含有重复数字的节点。
示例 1:
输入: 1->3->2->3->5->4->4 输出: 1->3->2->5->4 示例 2:
输入: 1->1->1->2->3 输出: 1->2->3
这种情况下就需要对元素值进行hash，如果不存在则忽略元素
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates(head *ListNode) *ListNode {
h:=&ListNode{}
h.Next=head
cur:=head
m:=make(map[int]int)
next:=cur.Next
for cur!=nil && next!=nil{
m[cur.Val]++
if m[next.Val]==0{
cur=next
next=next.Next
}else{
cur.Next=next.Next
next=next.Next
}
}
if next!=nil && m[next.Val]==0 {
cur.Next=next
}else{
cur.Next=nil
}
return h.Next
}三、删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5示例 2:
输入: 1->1->1->2->3
输出: 2->3解题思路：
1，始终要让pre在cur的前面，通过判断cur.val == cur.next.val判断重复元素是否存在。
2，为了简化，给链表加一个头部
h -> 1 -> 2 3 3 4 -> 4 -> 5
| |
pre cur
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates(head *ListNode) *ListNode {
h:=&ListNode{}
h.Next=head
cur:=head
pre:=h
for cur!=nil{
flag:=false
for cur.Next!=nil && cur.Val==cur.Next.Val{
cur=cur.Next
flag=true
}
if flag{
pre.Next=cur.Next
}else{
pre.Next=cur
pre=cur
}
cur=cur.Next
}
return h.Next
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-03-25，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读
腾讯云开发者
