1 题目
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
(注: 来自leetcode)
2 解法一
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* deleteDuplicates(struct ListNode* head){
struct ListNode* cur = head;
struct ListNode* root = NULL; // root 表示要返回的元素指针, 赋值给第一个唯一元素, 可以通过NULL来做判断是否为第一次赋值
struct ListNode* pre = NULL; // 上一个唯一元素, 当找到一个唯一元素, 需要与上一个唯一元素连接起来
while(cur) {
bool cur_delete_flag = false; // 表示当前该元素是否该删除
while (cur && cur->next && cur->val == cur->next->val) { // 循环出所有相等的元素
cur = cur->next;
cur_delete_flag = true;
}
if (!cur_delete_flag) {
if (root == NULL) { // 表示第一个唯一的元素
root = cur;
}
if (pre) {
pre->next = cur; // 与上一个唯一元素连接起来
}
pre = cur;
} else {
if (pre) {
pre->next = cur->next; // 舍弃掉相同的元素
}
}
cur = cur->next;
}
return root;
}
3 解法二
解法2加了一个头节点, 让行为相对统一
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* deleteDuplicates(struct ListNode* head) {
if (head == NULL || head->next == NULL) { // 假如是空或者只有一个元素就不用比较了
return head;
}
struct ListNode tmp; // 作为头节点来表示第一个唯一元素
struct ListNode* pre = &tmp; // 表示上一个唯一元素
pre->next = head;
struct ListNode* iter = pre->next->next;
bool mark = false;
while(iter != NULL){
if (pre && pre->next->val == iter->val) {// 比较的是上一个唯一的元素的后面元素是否相等
pre->next->next = iter->next; // 如果相等删除当前元素, 但不能删除pre->next, 留作后面的比较
mark = true;
} else { // 如果不相等
if (mark) { // 说明pre->next相同过, pre不能改变, 但是要删除pre->next
pre->next = iter;
mark = false;
} else { // 说明pre->next是唯一的元素, 要更新pre以及
pre = pre->next;
}
}
iter = iter->next;
}
if (mark) { // 表示上pre->next相同过, 需要删除
pre->next = NULL;
}
return tmp.next;
}
解法3
解法3和解法2类似, 只是多加了一层循环来找出与当前元素值不同的元素, 简洁了很多.
struct ListNode* deleteDuplicates(struct ListNode* head){
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode tmp;
struct ListNode* pre = &tmp;
pre->next = head;
struct ListNode* cur = pre->next;
while(cur) {
while(cur && cur->next && cur->val == cur->next->val){ // 移动cur一直到与cur->next值不同
cur = cur->next;
}
if (pre->next == cur) { // 表示cur没移动过, 也就是唯一的元素值
pre = cur;
} else {
pre->next = cur->next;
}
cur = cur->next;
}
return tmp.next;
}
网友评论