【LeetCode算法】第83题:删除排序链表中的重复元素
目录
一、题目描述
二、初次解答
三、官方解法
四、总结
一、题目描述
二、初次解答
1. 思路:双指针法,只需遍历一遍。使用low指向前面的元素,high用于查找low后面与low不同内容的节点。将具有不同内容的节点链接在low后面,实现重复元素的删除。
2. 代码:
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ struct ListNode* deleteDuplicates(struct ListNode* head) {if(!head)return NULL;struct ListNode* low=head, *high=head;for(;high;high=high->next){if(high->val!=low->val){low->next=high;low=high;}}low->next=NULL;return head; }
3. 优点:若存在多个连续重复的节点,提高了删除的效率,个人感觉在这种场景下是比官方的单指针遍历方法要快的。
4. 缺点:对于重复元素较少的链表,会给low重复赋值,因此在这种场景下会降低效率。
三、官方解法
1. 思路:单指针遍历。使用单个指针来遍历链表,将当前指向节点的内容与下一个节点的内容作比较,若相等则删除下一个节点。
2. 代码:
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ struct ListNode* deleteDuplicates(struct ListNode* head) {if(!head)return NULL;struct ListNode* cur=head;while(cur->next){if(cur->val==cur->next->val){cur->next=cur->next->next;}else{cur=cur->next;}}return head; }
3. 优点:对于重复元素较少的链表,单个指针会直接往后走不会执行其他操作,因此这种场景下效率高。(对应上述双指针法的缺点)
4. 缺点:若存在多个连续重复的节点,删除节点的效率不如双指针法。(对应上述双指针法的优点)
四、总结
删除有序链表的重复节点,可以使用双指针法或单指针法。