【算法】删除链表中重复元素

本题来源---《删除链表中重复元素》。

题目描述

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

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* deleteDuplicates(struct ListNode* head)
{}

关于本题，我整理了两种解题方法：

第一种：单指针

第二种：双指针

第一种：单指针

解题思路：

（1）声明一个指针指向头结点，比较cur指向的data域与cur->next指向的data域是否相等。

（2）如果相等，则删除该结点。

 （3）如果不相等，移动cur指针，继续比较。

 代码如下：

struct ListNode* deleteDuplicates(struct ListNode* head)
{struct ListNode     *cur,*tmp;cur = head;if( !head ){return NULL;}while( cur->next ){if( cur->val == cur->next->val ){tmp = cur->next;cur->next = cur->next->next;free(tmp);}else{cur = cur->next;}}return head;
}

复杂度分析

        时间复杂度：O(n)

        空间复杂度：O(1)

第二种：双指针

解题思路：

（1）声明两个指针，第一个指针cur指向head，第二个指针ptr指向head->next。比较cur指向的data域与ptr指向的data域是否相等。

 （2）如果相等，则删除该结点。

 （3）如果不相等，移动cur、ptr指针，继续比较。

代码如下：

struct ListNode* deleteDuplicates(struct ListNode* head)
{struct ListNode     *cur,*ptr,*tmp;if( !head ){return NULL;}cur = head;ptr = head->next;while( ptr ){if( cur->val != ptr->val ){cur = cur->next;ptr = ptr->next;}else{tmp = ptr;cur->next = ptr->next;ptr = ptr->next;free(tmp);}}return head;
}

复杂度分析

        时间复杂度：O(n)

        空间复杂度：O(1)