AcWing 29：删除链表中重复的节点

【题目来源】
https://www.acwing.com/problem/content/27/

【题目描述】
在一个排序的链表中，存在重复的节点，请删除该链表中重复的节点，重复的节点不保留。

【数据范围】
链表中节点 val 值取值范围 [0,100]。
链表长度 [0,100]。

【样例1】
输入：1->2->3->3->4->4->5
输出：1->2->5

【样例2】
输入：1->1->1->2->3
输出：2->3

【算法分析】
● 结构体构造函数：https://blog.csdn.net/hnjzsyjyj/article/details/139553390
结构体的两种写法如下表所示。

● 在本例中，链表已经确定且结点值已排序。由于首元结点 head 的值可能重复，故新建一个结点 L 指向首元结点 head。如果首元结点 head 的值重复的话，则改变结点 L 的 next 指向。

【算法代码】
本例代码以核心代码模式给出。

/**
 * Definition for singly-linked list.
 * struct ListNode{
 *     int val;
 *     ListNode *next;
 *     ListNode(int x):val(x),next(NULL){}
 * };
 */

class Solution {
    public:
        ListNode* deleteDuplication(ListNode* head) {
            auto L=new ListNode(-1);
            L->next=head;
            auto p=L;

            while(p->next) {
                auto q=p->next;
                while(q->next && q->next->val==p->next->val) q=q->next;
                if(q==p->next) p=q;
                else p->next=q->next;
            }

            return L->next;
        }
};

【参考文献】
https://www.acwing.com/solution/content/23660/
https://www.acwing.com/solution/content/735/
https://www.acwing.com/solution/content/53539/


 

原文地址：https://blog.csdn.net/hnjzsyjyj/article/details/143650278

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！