菜鸟笔记
提升您的技术认知

剑指offer

《剑指Offer》刷题目笔记

剑指Offer 数组

《剑指Offer》二维数组中的查找《剑指Offer》旋转数组的最小数字《剑指Offer》调整数组顺序使奇数位于偶数前面《剑指Offer》数组中出现次数超过一半的数字《剑指Offer》连续子数组的最大和《剑指Offer》把数组排成最小的数《剑指Offer》数组中的逆序对《剑指Offer》数字在排序数组中出现的次数《剑指Offer》数组中只出现一次的数字《剑指Offer》数组中重复的数字《剑指Offer》构建乘积数组

剑指Offer 字符串

《剑指Offer》替换空格《剑指Offer》字符串的排列《剑指Offer》第一个只出现一次的字符《剑指Offer》左旋转字符串《剑指Offer》翻转单词顺序序列《剑指Offer》把字符串转换成整数《剑指Offer》正则表达式匹配《剑指Offer》表示数值的字符串

剑指Offer 链表

《剑指Offer》从尾到头打印链表《剑指Offer》链表中倒数第k个结点《剑指Offer》反转链表《剑指Offer》合并两个排序的链表《剑指Offer》复杂链表的复制《剑指Offer》两个链表的第一个公共结点《剑指Offer》链表中环的入口结点《剑指Offer》删除链表中重复的结点

剑指Offer 树

《剑指Offer》重建二叉树《剑指Offer》树的子结构《剑指Offer》二叉树的镜像《剑指Offer》从上往下打印二叉树《剑指Offer》二叉树中和为某一值的路径《剑指Offer》二叉树的深度《剑指Offer》平衡二叉树《剑指Offer》二叉树的下一个结点《剑指Offer》对称的二叉树《剑指Offer》按之字顺序打印二叉树《剑指Offer》把二叉树打印成多行《剑指Offer》序列化二叉树

《剑指Offer》删除链表中重复的结点

阅读 : 341

题目描述

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表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