• Total Accepted: 163106
• Total Submissions: 417745
• Difficulty: Easy
• Contributors: Admin

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.

来源： 

分析

---

使用双指针， pre 和 cur，非递归

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

/**   * 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 == NULL || head->next == NULL)  return  head;                    ListNode* pre = head;          ListNode* cur = head->next;          while (cur != NULL){              if (cur->val == pre->val){                  ListNode * tmp = cur;                  cur = cur->next;                  pre->next = cur;                  delete  tmp;              }              else {                  pre = pre->next;                  cur = cur->next;              }          }          return  head;      } };

递归法

删除head之后的list中重复元素，

然后再比较，如果head->val == head->next->val

则返回head->next

1 2 3 4 5 6 7 8 9 10 11 12 13

class  Solution { public :      ListNode* deleteDuplicates(ListNode* head) {           if (head == NULL || head->next == NULL)  return  head;           head->next = deleteDuplicates(head->next);           if (head->next->val == head->val){              ListNode* tmp = head;              head = head->next;              delete  tmp;           }           return  head;      } };