题目描述

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。返回同样按升序排列的结果链表。

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

  • 2021/03/26

    法一：直接遍历链表

  • easy题直接重拳出击

    • 新建一个哑节点，指向head；
    • 再新建一个cur，移动cur 和 head判断是否需要加入链表
    • val值相等则直接前移head，否则都前移
  • 时间复杂度 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 or not head.next:
    9.           return head
    11.       dummy = ListNode(101)
    12.       cur = dummy
    13.       while head:
    14.           if cur.val != head.val:
    15.               cur.next = head
    16.               cur = cur.next
    17.           head = head.next
    18.       cur.next = None
    19.       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.       ListNode* dummy = new ListNode(101, head);
    15.       ListNode* cur = dummy;
    17.       if (!head || !head->next) return head;
    19.       while (head) {
    20.           if (cur->val != head->val) {
    21.               cur->next = head;
    22.               cur = cur->next;
    23.           }
    24.           head = head->next;
    25.       }
    26.       cur->next = nullptr;
    27.       return dummy->next;
    28.   }
    29. };

    法二：递归

  • 递归终止条件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
    10.       if head.val != head.next.val: # 若不相等则用head.next 作为头继续递归
    11.           head.next = self.deleteDuplicates(head.next)
    12.       else: # 否则的话跳过相同的元素，将遇到的第一个不同的节点作为head进行递归
    13.           move = head.next
    14.           while move.next and head.val == move.next.val:
    15.               move = move.next
    16.           return self.deleteDuplicates(move)
    17.       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) return head;
    16.       if (head->val != head->next->val) {
    17.           head->next = deleteDuplicates(head->next);
    18.       } else {
    19.           ListNode* move = new ListNode(0);
    20.           move = head->next;
    21.           while (move->next && head->val == move->next->val) {
    22.               move = move->next;
    23.           }
    24.           return deleteDuplicates(move);
    25.       }
    27.       return head;
    28.   }
    29. };