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: 85697

 

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 };