83. 删除排序链表中的重复元素（双指针法（快慢指针），单指针法，递归法）

53 阅读 0 评论 35 点赞

我是靠谱客的博主精明毛豆，最近开发中收集的这篇文章主要介绍83. 删除排序链表中的重复元素（双指针法（快慢指针），单指针法，递归法），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：双指针法（快慢指针）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        //双指针方法
        if(!head||!head->next){
            return head;
        }
        ListNode*quick = head->next;
        ListNode*slow = head;
        while(slow->next!=NULL){
            if(slow->val==quick->val){
                if(!quick->next){
                    slow->next=NULL;
                }else{
                    slow->next=quick->next;
                    quick = quick->next;
                }
            }else{
                slow=slow->next;
                quick = quick->next;
            }
        }
        return head;
    }
};

方法二：单指针法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        //单指针方法
        if(!head||!head->next){
            return head;
        }
        ListNode*tmp=head;
        while(tmp->next&&tmp){
            if(tmp->val==tmp->next->val){
                if(tmp->next->next){
                    tmp->next = tmp->next->next;
                    // tmp = tmp->next;
                }else{
                    tmp->next = NULL;
                }
            }else{
                tmp = tmp->next;
            }
        }
        return head;
    }
};

方法3：递归法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        //递归方法
        if(!head||!head->next){
            return head;
        }
        head->next = deleteDuplicates(head->next);
        if(head->val==head->next->val){
            head = head->next;
        }
        return head;
    }
};