【python】Leetcode每日一题-删除排序链表中的重复元素2

【python】Leetcode每日一题-删除排序链表中的重复元素2

【题目描述】

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

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

示例1：

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

示例2：

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

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

【分析】

• 思路：

  利用栈+标记，遍历一遍链表节点，如果栈中无此节点值，将值压入栈，并给予初始标记0，如果有此节点值，则表示已存在，不将节点压入栈中，并标记对应栈中值的标记为1。

  最后遍历一遍栈，如果对应标记为0则添加新链表的节点。

• 单调栈

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, val=0, next=None):
  #         self.val = val
  #         self.next = next
  
  class Solution:
      def deleteDuplicates(self, head: ListNode) -> ListNode:
          all = []
          flag = []
          while head != None:
              if head.val not in all:
                  all.append(head.val)
                  flag.append(0)
              else:
                  index = all.index(head.val)
                  flag[index] = 1
              head = head.next
          p = ListNode()
          head = p
          k = p
          flag_ = False
          for i in range(len(all)):
              if flag[i] == 0:
                  flag_ = True
                  p.val = all[i]
                  q = ListNode()
                  p.next = q
                  k = p
                  p = q
          if flag_:
              k.next = None
          else:
              head = None
          return head
  

• 看了一位兄弟的评论，感觉比官方的全：

  • hash_map

    其实就是标记，但是这样的话时间复杂度和空间复杂度都低很多。

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            if (!head || !head->next)
                return head;
            
            unordered_map mp;
            ListNode* cur = head;
            while (cur) {
                mp[cur->val]++;
                cur = cur->next;
            }
            
            cur = head;
            ListNode* dummy = new ListNode(-1);
            ListNode* res = dummy;
            while (cur) {
                if (mp[cur->val] == 1) {
                    dummy->next = new ListNode(cur->val);
                    dummy = dummy->next;
                }
                cur = cur->next;
            }
            return res->next;
        }
    };
    

  • 哑头节点

    即官方解法（自己忽略了递增序列，麻烦了很多

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            if (!head || !head->next)
                return head;
            
            ListNode* dummy = new ListNode(-1);
            dummy->next = head;
            
            ListNode* pre = dummy;
            ListNode* cur = head;
            while (cur && cur->next) {
                if (cur->val == cur->next->val) {
                    while (cur->next && cur->val == cur->next->val) {
                        cur = cur->next;
                    }
                    pre->next = cur->next;
                    cur = cur->next;
                } else {                
                    pre = cur;
                    cur = cur->next;
                }
            }
            return dummy->next;
        }
    };
    

  • 递归

    思路和dummy头节点一样，只是实现思路不同

    值不同时递归，值相同时pass

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            if (!head) 
                return head;
            
            if (head->next && head->val == head->next->val) {
                while (head->next && head->val == head->next->val) {
                    head = head->next;
                }
                return deleteDuplicates(head->next);
            } else {
                head->next = deleteDuplicates(head->next);
            }
            
            return head;
        }
    };