[leetcode题解]82.Remove Duplicates from Sorted List-II(排序链表保留唯一)

上一篇论文中写了一个排序链表去重的题目解法,那个题目要求对于重复的元素只保留一个,而本题给定一个排序链表,要求把重复的元素全部删除,所以与上个题目有点差异,但是解法可以基本一致,这里对每个元素,判断其是否唯一,如果不唯一就直接删除,如果唯一,那么就将这个唯一的元素拿出来插入新的链表中,最后将新的链表返回去即可。

题意演示

Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

c++代码:

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) 
    {
        if (head == NULL)return head;
        
        ListNode *pre = new ListNode(-1);
        pre->next = NULL;
        
        ListNode *p = head, *tail = pre, *q = NULL;
        while(p!= NULL)
        {
        //先看下是否相同
            q = p->next;
            if (q == NULL || q->val != p->val)
            {
                tail->next = p;
                tail = tail->next;
                p = q;
                continue;
            }
            //如果相同,则一直找到不同元素为止
            while(q != NULL && q->val == p->val)q = q->next;
            p = q;
        }
        tail->next = NULL;
        return pre->next;
    }
};

python代码:

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        :author: 凌风技术站-iaccepted
        """
        if head is None:
            return head
            
        pre = ListNode(-1)
        tail = pre
        
        #把所有唯一出现的节点插入一个新链表中即可
        q = head
        while q is not None:
            #下面找当前节点q及后续节点有几个值是相同的
            n = 0
            p = q
            while p is not None and p.val == q.val:
                p = p.next
                n += 1
                
            #若n=1,则说明当前节点的值唯一
            if n == 1:
                tail.next = q
                tail = q
            q = p
        tail.next = None
        return pre.next

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]82.Remove Duplicates from Sorted List-II(排序链表保留唯一)

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/90.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注