83. 删除排序链表中的重复元素
题目描述
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2]
输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
解题方案
- C 遍历链表，只需比较当前节点和下一个节点的值
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* deleteDuplicates(struct ListNode* head) { struct ListNode* temp = head; if (head == NULL) return head; while (temp && temp->next) { if (temp->val == temp->next->val) { temp->next = temp->next->next; } else { temp = temp->next; } } return head; }
- C 递归实现
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* deleteDuplicates(struct ListNode* head) { if (head == NULL || head->next == NULL) return head; head->next = deleteDuplicates(head->next); if (head->val == head->next->val) { return head->next; } else { return head; } return head; }
82. 删除排序链表中的重复元素Ⅱ
题目描述
给定一个已排序的链表的头 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
- 题目数据保证链表已经按升序 排列
解题方案
- C
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* deleteDuplicates(struct ListNode* head) { if (head == NULL) { return head; } // 定义一个新节点用来指向头节点，以防头节点被删除 struct ListNode* pre = (struct ListNode*)malloc(sizeof(struct ListNode)); pre->next = head; // 将新节点指向头节点 struct ListNode* temp = pre; // 定义一个临时链表指针指向新节点 while (temp->next && temp->next->next) { if (temp->next->val == temp->next->next->val) { int value = temp->next->val; // 保存这个值 while (temp->next && temp->next->val == value) { temp->next = temp->next->next; // 删除相同节点 } } else { temp = temp->next; } } return pre->next; }
复杂度分析：
时间复杂度为 O(n)，其中 n 是链表的长度。
空间复杂度为 O(1)。
