《剑指offer》删除链表中重复的结点-ag真人游戏

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。

解题思路

删除重复结点，只需要记录当前结点前的最晚访问过的不重复结点ppre、当前结点pcur、指向当前结点后面的结点pnext的三个指针即可。如果当前节点和它后面的几个结点数值相同，那么这些结点都要被剔除，然后更新ppre和pcur；如果不相同，则直接更新ppre和pcur。

需要考虑的是，如果第一个结点是重复结点我们该怎么办？这里我们分别处理一下就好，如果第一个结点是重复结点，那么就把头指针phead也更新一下。

代码实现(c )

/*
struct listnode {
    int val;
    struct listnode *next;
    listnode(int x) :
        val(x), next(null) {
    }
};
*/
class solution {
public:
    listnode* deleteduplication(listnode* phead)
    {
        if(phead == null){
            return null;
        }
        // 指向当前结点前最晚访问过的不重复结点
        listnode* ppre = null;
        // 指向当前处理的结点
        listnode* pcur = phead;
        // 指向当前结点后面的结点
        listnode* pnext = null;
        while(pcur != null){
            // 如果当前结点与下一个结点相同
            if(pcur->next != null && pcur->val == pcur->next->val){
                pnext = pcur->next;
                // 找到不重复的最后一个结点位置
                while(pnext->next != null && pnext->next->val == pcur->val){
                    pnext = pnext->next;
                }
                // 如果pcur指向链表中第一个元素，pcur -> ... -> pnext ->... 
                // 要删除pcur到pnext, 将指向链表第一个元素的指针phead指向pnext->next。
                if(pcur == phead){
                    phead = pnext->next;
                }
                // 如果pcur不指向链表中第一个元素，ppre -> pcur ->...->pnext ->... 
                // 要删除pcur到pnext，即ppre->next = pnext->next
                else{
                    ppre->next = pnext->next;
                }
                // 向前移动
                pcur = pnext->next;
            }
            // 如果当前结点与下一个结点不相同
            else{
                ppre = pcur;
                pcur = pcur->next;
            }
        }
        return phead;
    }
};

代码实现(python)

# -*- coding:utf-8 -*-
# class listnode:
#     def __init__(self, x):
#         self.val = x
#         self.next = none
class solution:
    def deleteduplication(self, phead):
        # write code here
        ppre = none
        pcur = phead
        pnext = none
        while pcur != none:
            if pcur.next != none and pcur.val == pcur.next.val:
                pnext = pcur.next
                while pnext.next != none and pnext.next.val == pcur.val:
                    pnext = pnext.next
                if pcur == phead:
                    phead = pnext.next
                else:
                    ppre.next = pnext.next
                pcur = pnext.next
            else:
                ppre = pcur
                pcur = pcur.next
        return phead