首页 > 代码库 > LeetCode: Remove Duplicates from Sorted List

LeetCode: Remove Duplicates from Sorted List

LeetCode: 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.

地址:https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/

算法:不算什么难题,直接看代码:

 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 || head->next == NULL) return head;13         ListNode *p = head;14         while(p->next){15             if(p->next->val == p->val){16                 ListNode *q = p->next;17                 p->next = q->next;18                 free(q);19             }else{20                 p = p->next;21             }22         }23         return head;24     }25 };

第二题:

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.

地址:https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

算法:这一题比上面一题稍微麻烦一点,但也不算很难,代码:

 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 || head->next == NULL) return head;13         ListNode *pre = NULL;14         ListNode *p = head;15         while(p){16             ListNode *q = p->next;17             while(q && q->val == p->val){18                 q = q->next;19             }20             if(p->next == q){21                 pre = p;22                 p = p->next;23             }else{24                 if(pre){25                     pre->next = q;26                 }else{27                     head = q;28                 }29                 while(p != q){30                     ListNode *tempP = p->next;31                     free(p);32                     p = tempP;33                 }34                 p = q;35             }36         }37         return head;38     }39 };

 

LeetCode: Remove Duplicates from Sorted List