Day10 | 删除排序链表中的重复元素 排序链表

第十天哈希表真好。删除排序链表中的重复元素题目给定一个已排序的链表删除所有重复的元素使得每个元素只出现一次。返回处理后的链表。解法一无脑哈希表思路很简单用一个HashSet存储出现过的值遍历链表发现重复就跳过否则加入集合并保留节点。这哈希表好哇得学得学。public class Solution { public ListNode DeleteDuplicates(ListNode head) { if (head null) return null; HashSetint table new HashSetint(); ListNode Poi_1 head; ListNode Poi_2 head.next; table.Add(head.val); while (Poi_2 ! null) { if (table.Contains(Poi_2.val)) { Poi_1.next Poi_2.next; } else { table.Add(Poi_2.val); Poi_1 Poi_2; } Poi_2 Poi_2.next; } return head; } }解法二直接遍历比较既然链表是排序的重复值一定连续出现。我们可以直接用单指针比较当前节点和下一个节点的值。public class Solution { public ListNode DeleteDuplicates(ListNode head) { if (head null) return null; ListNode Poi head; while (Poi ! null Poi.next ! null) { if (Poi.val Poi.next.val) { Poi.next Poi.next.next; } else { Poi Poi.next; } } return head; }连续性这种条件感觉用来配合下标或者前后都是很好用的就比如说一个连续数列可以配合for的下标选出重复数字或者缺少数字。排序链表题目给你链表的头结点head请将其按升序排列并返回排序后的链表。解法利用数组官方解法看的云里雾里就不放了放一个自己脑子寻思的吧“暴力一点”的写法取出所有节点用数组排序再重新串起来。毕竟数组列表之类的可以自己排序就可以不用考虑排序的问题了代码量还少。时间复杂上一样但是空间耗得多一点。public class Solution { public ListNode SortList(ListNode head) { if (head null) return null; ListListNode nodes new ListListNode(); ListNode poi head; while (poi ! null) { nodes.Add(poi); poi poi.next; } nodes.Sort((a, b) a.val.CompareTo(b.val)); for (int i 0; i nodes.Count - 1; i) { nodes[i].next nodes[i 1]; } nodes[nodes.Count - 1].next null; return nodes[0]; } }