题目描述

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

  • 地址：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii

  • 2021/03/25

    法一：直接遍历链表

  • 因为head有可能会被删除，新建一个虚拟节点指向head进行遍历

    • 依题意链表是有序的，若相同必定出现在相邻的位置
    • 即 cur->next == cur->next->next 时就应该删除该节点，并用一个变量 tmp 记录下被删除的节点的值，用于判断->next->next->next是否需要删除
  • 时间复杂度 O(n)

  • 空间复杂度 O(1) 

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. #     def __init__(self, val=0, next=None):
    4. #         self.val = val
    5. #         self.next = next
    6. class Solution(object):
    7.   def deleteDuplicates(self, head):
    8.       if not head:
    9.           return head
    11.       dummy = ListNode(0, head)
    12.       cur = dummy
    14.       while cur.next and cur.next.next:
    15.           if cur.next.val == cur.next.next.val:
    16.               tmp = cur.next.val
    17.               while cur.next and cur.next.val == tmp:
    18.                   cur.next = cur.next.next
    19.           else:
    20.               cur = cur.next
    21.       return dummy.next
    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     ListNode *next;
    6. *     ListNode() : val(0), next(nullptr) {}
    7. *     ListNode(int x) : val(x), next(nullptr) {}
    8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9. * };
    10. */
    11. class Solution {
    12. public:
    13.   ListNode* deleteDuplicates(ListNode* head) {
    14.       if (!head) return head;
    16.       ListNode* dummy = new ListNode(0, head); // 新建一个指向head的值为0的dummy节点
    17.       ListNode* cur = dummy;
    19.       while (cur->next && cur->next->next) { // 一开始就是原链表头节点和头节点的下一个节点
    20.           if (cur->next->val == cur->next->next->val) { // 相邻的两个节点值相等
    21.               int tmp = cur->next->val; // 记录下节点的值
    22.               while ((cur->next) && (cur->next->val == tmp)) { // cur 前移
    23.                   cur->next = cur->next->next;
    24.               }
    25.           }
    26.           else {
    27.               cur = cur->next;
    28.           }
    29.       }
    30.       return dummy->next;
    31.   }
    32. };

    法二：递归

  • 递归终止条件head为空 或者 只有一个节点，return head

    • 若相邻的不相等，那么递归head->next
    • 若相邻的相等，那么就递归移动后的，所以要判断一下
  • 时间复杂度：O(n)

  • 空间复杂度：O(n)

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. #     def __init__(self, val=0, next=None):
    4. #         self.val = val
    5. #         self.next = next
    6. class Solution(object):
    7.   def deleteDuplicates(self, head):
    8.       if not head or not head.next:
    9.           return head
    11.       if head.val != head.next.val:
    12.           head.next = self.deleteDuplicates(head.next)
    13.       else:
    14.           move = head.next
    15.           while move and head.val == move.val:
    16.               move = move.next
    17.           return self.deleteDuplicates(move)
    18.       return head
    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     ListNode *next;
    6. *     ListNode() : val(0), next(nullptr) {}
    7. *     ListNode(int x) : val(x), next(nullptr) {}
    8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9. * };
    10. */
    11. class Solution {
    12. public:
    13.   ListNode* deleteDuplicates(ListNode* head) {
    14.       if (!head || !head->next) {
    15.           return head;
    16.       }
    18.       if (head->val != head->next->val) {
    19.           head->next = deleteDuplicates(head->next);
    20.       }
    21.       else {
    22.           ListNode* move = head->next;
    23.           while (move && head->val == move->val) {
    24.               move = move->next;
    25.           }
    26.           return deleteDuplicates(move);
    27.       }
    29.       return head;
    30.   }
    31. };