【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. 缺点：若存在多个连续重复的节点，删除节点的效率不如双指针法。（对应上述双指针法的优点）

四、总结

删除有序链表的重复节点，可以使用双指针法或单指针法。