锻练编程思维——每日一题：《剑指offer》删除链表中重复的结点

小咪咪 2023-02-15 03:49 7阅读 0赞

# 题目描述 #

题目描述  
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5  
题目所给代码框架：

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
            val(x), next(NULL) {
        }
    };
    */
    class Solution {
        
    public:
        ListNode* deleteDuplication(ListNode* pHead)
        {
        
    
        }
    };

# 题目解析 #

核心思想：查找重复的结点链，**用一个指针p指向重复的结点链中第一个结点前的那个结点**，**用另一个指针q趟过重复的结点链(据题目来看重复的结点都挨在一起）**，然后让p->next=q;  
分步思想：

*  根据核心思想来看，**需要有一个指针去指向重复的结点链中第一个结点前的那个结点**，为什么呢？**因为你让某个指针去趟重复的结点链去了，如果只有这个结点指针，那么我怎么找到重复的结点链中第一个结点前的那个结点？**
 *  因为要试探有没有重复的结点链，所以我们需要一个遍历链表的指针。所以目前我们需要三个指针。
 *  这些指针一开始应该指向哪里呢？如果需要有一个指针去指向重复的结点链中第一个结点前的那个结点，以便这个指针指的结点的next域是重复的结点链的最后一个结点的下一个结点。**那么我应该需要一个结点（指针）去存放这个指针的指向**，目前我们需要四个指针
 *  然后我们怎么去用另一个指针q趟过重复的结点链(据题目来看重复的结点都挨在一起），然后让p->next=q;呢？
 *  就是利用循环，在遍历单链表的时候，检查当前节点与下一点是否为相同值，如果相同，继续查找相同值的最大长度，然后指针改变指向。
 *  循环条件和if条件里的cur->next是必要的，因为一旦next域为空，就没有后面的当前结点值和后一结点值的比较，避免发生低级错误。、
 *  所以定义三个指针，qHead（也可以看作是个**存放指针指向**的结点），pre，cur，**qHead结点（指针）用来存放pre指针的指向**，**pre指针用来指向重复的结点链中第一个结点前的那个结点**，cur作为链表的遍历指针，
 *  cur指针只要不指向空结点，就不断判断cur指针指向的结点的next域空不空，不空，比较cur指针所指结点的值和cur指针所指结点的后继结点的值。
    
     *  如果比较cur指针所指结点的值和cur指针所指结点的后继结点的值**相等**，则cur指针链表后头走**直到cur指针所指结点的值和cur指针所指结点的后继结点的值不等**，此时cur指针再往后走一个结点，**让重复的结点链中第一个结点前的那个结点（由pre指针指向）的next域指向cur指针指的结点。即pre->next=cur;这样就跳过了2~n个重复的结点，达到了删除链表中重复的结点的目的。**
     *  如果比较cur指针所指结点的值和cur指针所指结点的后继结点的值**不相等**，则**让pre指针和cur指针同步后移一个结点。** 然后**再看cur所指结点是不是空结点**，**再比较cur指针所指结点的值和cur指针所指结点的后继结点的值**  
        就这么一个思路。多看几遍代码吧，有的东西不好说清楚。多看多写你自然就懂了这个思想和套路

# 题解代码 #

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
            val(x), next(NULL) {
        }
    };
    */
    class Solution {
        
    public:
        ListNode* deleteDuplication(ListNode* pHead)
        {
        
            ListNode *qHead=new ListNode(0);//用来安放pre指针的指向，为后面查找
            //并删除链表中重复的结点做准备。
            qHead->next=pHead;
            ListNode *pre=qHead,*cur=pHead;
            while(cur)
            {
        
                if(cur->next&&cur->val==cur->next->val)
                {
        
                    cur=cur->next;
                    while(cur->next&&cur->val==cur->next->val)//注意这里也要判定
                        //cur的next域空不空！空的话直接退出这个逻辑表达式！不会再有
                        //当前结点和next结点的值比较
                    {
        
                        cur=cur->next;
                    }
                    cur=cur->next;
                    pre->next=cur;
                }
                else
                {
        
                    pre=pre->next;
                    cur=cur->next;
                }
            }
            return qHead->next;
            
        }
    };