/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeDuplicateNodes(ListNode* head) {
}
};
面试题 02.01. 移除重复节点
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入：[1, 2, 3, 3, 2, 1] 输出：[1, 2, 3]
示例2:
输入：[1, 1, 1, 1, 2] 输出：[1, 2]
提示：
进阶：
如果不得使用临时缓冲区，该怎么解决？
原站题解
golang 解法, 执行用时: 292 ms, 内存消耗: 6 MB, 提交时间: 2021-06-11 15:14:39
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeDuplicateNodes(head *ListNode) *ListNode {
ob := head
for ob != nil {
oc := ob
for oc.Next != nil {
if oc.Next.Val == ob.Val {
oc.Next = oc.Next.Next
} else {
oc = oc.Next
}
}
ob = ob.Next
}
return head
}
golang 解法, 执行用时: 16 ms, 内存消耗: 6.2 MB, 提交时间: 2021-06-11 15:12:32
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeDuplicateNodes(head *ListNode) *ListNode {
if head == nil {
return head
}
mp := map[int]bool{head.Val: true}
pos := head
for pos.Next != nil {
cur := pos.Next
if !mp[cur.Val] {
mp[cur.Val] = true
pos = pos.Next
} else {
pos.Next = pos.Next.Next
}
}
pos.Next = nil
return head
}