首页 > 代码库 > Remove Duplicates from Sorted List I&&II
Remove Duplicates from Sorted List I&&II
Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
这题思路很清楚，当前节点的值与前一节点的值相同，那么就直接删掉
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 ListNode *deleteDuplicates(ListNode *head) {12 if( !head ) return 0;13 ListNode* pre = head; //前驱14 ListNode* cur = pre->next; //当前15 while( cur ) {16 if( cur->val == pre->val ) { //若与前驱相同，直接删掉17 ListNode* p = cur;18 cur = cur->next;19 pre->next = cur;20 delete p;21 } else { //不同直接下移22 cur = cur->next;23 pre = pre->next;24 }25 }26 return head;27 }28 };
Remove Duplicates from Sorted List II
Total Accepted: 21273 Total Submissions: 85697My Submissions
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.
凡是重复的数据都要删除，可以设个标记，如果发现有重复节点，那么将其值赋予标记上，然后凡是遇到标记值的节点直接删除
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 ListNode *deleteDuplicates(ListNode *head) {12 if( !head ) return 0;13 const int INF = 0x3fffffff; //设置个不可能值14 ListNode node(-1); //布置头节点，便于删除15 node.next = head;16 ListNode* pre = &node;17 ListNode* cur = head;18 int needDelete = INF; //便于逻辑判断19 while( cur ) {20 if( cur->val == needDelete ) { //若等于需被删除值，那么直接删除21 ListNode* p = cur;22 cur = cur->next;23 pre->next = cur;24 delete p;25 } else if( cur->next && cur->val == cur->next->val ) { //若发现有重复元素，那么记录需要删除的值26 needDelete = cur->val;27 } else { //后移节点28 cur = cur->next;29 pre = pre->next;30 }31 }32 return node.next;33 }34 };
这里的不可能值，如果可能的话，那么就需要加逻辑判断，否则就会出大bug，尤其是面试官询问的话
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 ListNode *deleteDuplicates(ListNode *head) {12 if( !head ) return 0;13 ListNode node(-1); //布置头节点，便于删除14 node.next = head;15 ListNode* pre = &node;16 ListNode* cur = head;17 while( cur && cur->next && cur->val != cur->next->val ) {18 pre = cur;19 cur = cur->next;20 }21 if( !cur->next ) return node.next;22 int needDelete = cur->val;23 while( cur ) {24 if( cur->val == needDelete ) { //若等于需被删除值，那么直接删除25 ListNode* p = cur;26 cur = cur->next;27 pre->next = cur;28 delete p;29 } else if( cur->next && cur->val == cur->next->val ) { //若发现有重复元素，那么记录需要删除的值30 needDelete = cur->val;31 } else { //后移节点32 cur = cur->next;33 pre = pre->next;34 }35 }36 return node.next;37 }38 };
Remove Duplicates from Sorted List I&&II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。