[数据结构与算法]数据结构与算法5（排序链表中删除重复数字）

?1 问题

????????存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，重复数字只保留一次。

????????返回同样按升序排列的结果链表。

1.1 示例

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

????????输出：[1,2,3,4,5]

1.2 示例

????????输入：head = [1,1,1,2,3,3]

????????输出：[1,2,3]

2 思路

2.1 遍历

?图1 遍历

?2.2 递归

?图2 递归

3 编程

3.1 遍历

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head)
     {

        if (!head || !head->next) return head;

        ListNode* dummy = new ListNode(0, head);
        ListNode* prev  = dummy;
        while (head)
        {
            while (head->next && head->val == head->next->val)
            {
                head = head->next;
            }

            if (prev->next = head)
            {
                prev->next = head;
            }
            
            prev = head;
            head = head->next;
        }

        return dummy->next;
    }
};

3.2 递归

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head)
     {

        if (!head || !head->next) return head;

        if (head->val == head->next->val)
        {
            while (head->next && head->val == head->next->val)
            {
                head = head->next;
            }

            return deleteDuplicates(head);

        }
        else
        {
            head->next = deleteDuplicates(head->next);
        }

        return head;
    }
};