删除按升序排列的单链表中的所有重复元素

删除按升序排列的单链表中的所有重复元素

删除单链表中的所有重复元素

题目解决思路代码说明

题目

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。并返回同样按升序排列的结果链表。示例如下所示：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

解决思路

采用虚拟头节点和两个指针p、q解决。初始时刻，p指向虚拟头结点，q指针用于从head开始寻找不重复的节点，。先判断p节点后面的两个节点是否重复，如果是重复节点，继续向后寻找，直至找到不重复的点，并将q指向该不重复的节点，然后将p->next指向q。如果p节点后面的两个节点不是重复节点，则将p指针向前移动一位。重复第二步和第三步，直到结束，最后返回虚拟头节点的下一个节点。 代码

C++代码

# include 

struct ListNode {
    int val;
    ListNode *next;
    ListNode(): val(0), next(nullptr) {}
    ListNode(int val): val(val), next(nullptr) {}
    ListNode(int val, ListNode *next): val(val), next(next) {}
};


class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (nullptr == head) {
            return head;
        }

        ListNode ret(0, head);
        ListNode *p = &ret;
        ListNode *q;    // 用于寻找下一个不重复的节点

        while (p->next) {
            // 判断p后面的两个节点是否产生了重复
            if (p->next->next && p->next->val == p->next->next->val) {  // p后面的两个节点是重复节点
                q  = p->next->next;
                // 向后寻找，直至找到一个不重复的点
                while (q && q->val == p->next->val) {
                    q = q->next;
                }
                p->next = q;    // 此时q指向的点为不重复的点（或nullptr）
            } else {            // p后面的两个节点没有重复，将p向前移动一位
                p = p->next;
            }
        }
        return ret.next;
    }
};


int main() {
    ListNode *a = new ListNode(1);
    ListNode *b = new ListNode(2);
    ListNode *c = new ListNode(3);
    ListNode *d = new ListNode(3);
    ListNode *e = new ListNode(4);
    ListNode *f = new ListNode(4);
    ListNode *g = new ListNode(5);
    ListNode *head = a;

    a->next = b;
    b->next = c;
    c->next = d;
    d->next = e;
    e->next = f;
    f->next = g;

    printf("before delete: ");
    while (head) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("n");

    head = a;
    Solution *solution = new Solution();
    ListNode *ret = solution->deleteDuplicates(head);

    printf("after delete: ");
    while (ret) {
        printf("%d ", ret->val);
        ret = ret->next;
    }

    return 0;
}

python代码

# -*- coding: utf-8 -*-

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return head

        ret: ListNode = ListNode(0, head)
        p: ListNode = ret       # 虚拟头节点
        q: ListNode             # 用于寻找下一个不重复的节点
        while p.next:
            # 判断p后面的两个节点是否产生了重复
            if p.next.next and p.next.val == p.next.next.val:       # p后面的两个节点是重复节点
                q = p.next.next
                # 向后寻找，直至找到一个不重复的点
                while q and q.val == p.next.val:
                    q = q.next
                p.next = q      # 此时q指向的点为不重复的点（或nullptr）
            else:               # p后面的两个节点没有重复，将p向前移动一位
                p = p.next

        return ret.next


def main():
    a: ListNode = ListNode(1)
    b: ListNode = ListNode(2)
    c: ListNode = ListNode(3)
    d: ListNode = ListNode(3)
    e: ListNode = ListNode(4)
    f: ListNode = ListNode(4)
    g: ListNode = ListNode(5)

    a.next = b
    b.next = c
    c.next = d
    d.next = e
    e.next = f
    f.next = g
    head = a

    print("before delete: ", end='')
    while head:
        print(head.val, end=' ')
        head = head.next
    print()

    head = a
    solution: Solution = Solution()
    ret: ListNode = solution.deleteDuplicates(head)

    print('after delete: ', end='')
    while ret:
        print(ret.val, end=' ')
        ret = ret.next


if __name__ == "__main__":
    main()

说明

对应LeetCode第82题。链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/