株洲网站建设方案咨询,公需科目在哪个网站做,html5网站,公司部门等级划分文章目录 一、题目二、C# 题解 一、题目 编写代码#xff0c;移除未排序链表中的重复节点。保留最开始出现的节点。 点击此处跳转题目。
示例1: 输入#xff1a;[1, 2, 3, 3, 2, 1] 输出#xff1a;[1, 2, 3] 示例2: 输入#xff1a;[1, 1, 1, 1, 2] 输出#xff1a;[1, … 文章目录 一、题目二、C# 题解 一、题目 编写代码移除未排序链表中的重复节点。保留最开始出现的节点。 点击此处跳转题目。
示例1: 输入[1, 2, 3, 3, 2, 1] 输出[1, 2, 3] 示例2: 输入[1, 1, 1, 1, 2] 输出[1, 2] 提示
链表长度在[0, 20000]范围内。链表元素在[0, 20000]范围内。
进阶
如果不得使用临时缓冲区该怎么解决
二、C# 题解 使用哈希表记录出现的数字只需要一次遍历即可
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) { val x; }* }*/
public class Solution {public ListNode RemoveDuplicateNodes(ListNode head) {Dictionaryint, bool map new Dictionaryint, bool();ListNode p head, q; // 双指针q 指向 p 的后一个元素while (p ! null) {map[p.val] true; // 记录 p 指向的元素q p.next; // 更新 qif (q null) break;int v q.val; // 取出 p 指向的元素值// 依据 v 对 p 进行操作if (map.ContainsKey(v)) p.next q.next; // 重复值则跳过 qelse p q; // 非重复值p 挪下一位}return head;}
}时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( n ) O(n) O(n)。
如果不使用临时缓冲区则需要每个元素依次检查进行多次遍历
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) { val x; }* }*/
public class Solution {public ListNode RemoveDuplicateNodes(ListNode head) {ListNode p head, q; // 双指针while (p ! null) {int v p.val; // 取出 p 指向元素的值q p; // q p 代替 p进行遍历// 出现 v 则删否则跳到下一个while (q.next ! null) {if (q.next.val v) q.next q.next.next;else q q.next;}p p.next; // 更新 p}return head;}
}时间复杂度 O ( n 2 ) O(n^2) O(n2)。空间复杂度 O ( 1 ) O(1) O(1)。
