Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving onlydistinctnumbers from the original list.
For example,
Given1->2->3->3->4->4->5
, return1->2->5
.
Given1->1->1->2->3
, return2->3
.
是重复的元素就全部移掉,前面有一道是移掉多余的重复元素,保留一个。
这道题的关键就需要注意保存重复元素的前一个指针,这样才能移除元素。
考指针和链表的操作熟练程度。
/**
* 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(-1);
dummy.next = head;
ListNode *pre = &dummy;
ListNode *cur = head;
ListNode *post = head->next;
bool flag = false;
while (cur && post)
{
while (post && cur->val == post->val)
{
post = post->next;
flag = true;
}
if (flag == true) pre->next = post;
else pre = pre->next;
flag = false;
cur = post;
if (post) post = post->next;
}
//不能用return head, 因为如果head重复的话,需要删掉head,但是其实head还在内存中,没有删掉,不过改变了dummy->next的链表。
return dummy.next;
}
};
//2014-2-13 update
ListNode *deleteDuplicates(ListNode *head)
{
if (!head || !head->next) return head;
ListNode dummy(0);
ListNode *p = &dummy;
bool repeat = false;
for ( ;head->next; head = head->next)//记得步进head
{
if (head->val == head->next->val) repeat = true;
else
{
if (repeat) repeat = false;
else//不重复的才加入新的链表中
{
p->next = head;
p = p->next;
}
}
}
if (!repeat)//注意别漏掉
{
p->next = head;
p = p->next;
}
p->next = nullptr; //注意:删除结尾多余的节点。
return dummy.next;
}
分享到:
相关推荐
给一个链表,如果一个数属于重复数字,就把这个数删除,一个都不留。 解法一 迭代 只需要两个指针,一个指针 pre 代表重复数字的前边的一个指针,另一个指针 cur 用来遍历链表。d 代表哨兵节点,用来简化边界条件,...
链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/ 思路 由于是排序链表,所以只需判断当前节点的元素与下一个节点的元素是否相同,如果相同则将当前节点的指针指向大下个节点,如果不同...
remove-duplicates-from-sorted-list ii 83 删除排序链表中的重复元素 remove-duplicates-from-sorted-list 86 分隔链表 partition-list 92 反转链表 II reverse-linked-list-ii(Reverse a Sub-list) 141 环形链表...
删除排序链表中的重复元素 II(Remove Duplicates from Sorted List II) 2018.9.27 重建二叉树(Rebuild Binary Tree) 2018.9.28 把字符串转换成整数(Convert a string to an integer) 2018.10.8 树的子结构...
Remove Duplicates from Sorted List II题目: | 源码:标签:单向链表难度:中等 / Medium146. LRU Cache题目: | 源码:标签:哈希表,双向链表难度:中等 / Medium212. Word-Search-II题目: | 英文站源码:./...
删除排序数组中的重复项 27 Easy 移除元素 35 Easy 搜索插入位置 Linked List(链表) ID Difficulty Title Java Python 21 Easy Merge Two Sorted Lists 83 Easy Remove Duplicates from Sorted List 141 Easy Linked...
83.删除排序链表中的重复元素 (Remove Duplicates from Sorted List) 88.合并两个有序数组 (Merge Sorted Array) 100.相同的树 (Same Tree) 104.二叉树的最大深度 (Maximum Depth of Binary Tree) 118.杨辉三角 ...
83-删除排序链表中的重复元素:remove-duplicates-from-sorted-list 92-反转链表II:reverse-linked-listt-ii 141-环形链表:linked-list-cycle 142-环形链表:linked-list-cycle-ii 160-相交链表:intersection-of-two-...
使用额外的缓冲区从未排序的链表中删除重复项 细绳 确定字符串是否包含所有唯一字符 (CTCI) 在不使用额外缓冲区的情况下删除字符串中的重复字符 (CTCI) 检查 2 个字符串是否为字谜 (CTCI) 检查一个字符串是否是另一...
leetcode ...List(链表) ID Difficulty Title Python C++ Blog 21 Easy Merge Two Sorted Lists 83 * Remove Duplicates from Sorted List 141 * Linked List Cycle 160 * Intersection of Two Linke
leetcode ...List(链表) ID Difficulty Title Python C++ Blog 21 Easy Merge Two Sorted Lists 83 * Remove Duplicates from Sorted List 141 * Linked List Cycle 160 * Intersection of Two Linke
LeetCode 原创文章每周最少两篇,后续最新文章会在首发,视频首发,大家可以加我进交流群,技术交流或提意见都可以,欢迎Star! 帮助文档 帮助文档存放在Help文件夹下。...Remove Duplicates from Sorted Lis