首页 > 代码库 > LeetCode::Remove Duplicates from Sorted List II [具体分析]
LeetCode::Remove Duplicates from Sorted List II [具体分析]
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
这道题目是前一个题目的进化版,因为反复了的那个数字会被所有删去,这里面临一个多引入一个指针,来表征须要删除的节点的前一个节点,再多引入一个布尔值,
来标记究竟这个数字是不是反复了;假设反复,位于pos 以及 next_pos之间的节点必须都删除(闭区间),pre_pos 非常显然原地不动,当发现不是反复,那么pre_pos
向前走一格。
一个注意点:在思考链表类问题的时候,必须非常明白每一个指针标志着什么,而且须要再用到诸如a->next a->val时特别确信a != NULL, 这个必须考虑到边界条件,如
何时走到了最后,或者链表仅仅有一个节点或者没有节点,出现了特殊情况等等,这个是RUNTIME ERROR的关键问题
<span style="font-family: Arial, Helvetica, sans-serif;">ListNode *deleteDuplicates(ListNode *head) {</span>
if (head == NULL || head->next == NULL) return head; bool isDup; ListNode *pos = head, *next_pos = head; ListNode *pre_pos = new ListNode(0); ListNode *new_head = pre_pos; pre_pos->next = head; while (next_pos != NULL) { next_pos = next_pos->next; isDup = false; while (next_pos != NULL && pos->val == next_pos->val) { isDup = true; next_pos = next_pos->next; } if (isDup) { pre_pos->next = next_pos; pos = next_pos; } else { pre_pos = pre_pos->next; pos = pos->next; } } return new_head->next; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。