题目

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
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
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy =new ListNode(-1);
        dummy->next=head;
      	//申请一个头节点指向head
        int dup;
        ListNode* cur = dummy;
      	//cur一直指向的是链表中确定存在的值.
      	//cur指针先指向头节点
        while(cur->next&&cur->next->next)
        {//如果head和head->next存在则进入循环
            if(cur->next->val==cur->next->next->val)
            {//如果head的值和head->next的值相同,
                dup = cur->next->val;// 把这个值记下来
                while(cur->next && cur->next->val==dup)//找到最后一个等于dup的地方
                {
                    cur->next = cur->next->next; //修改cur的next域的指向位置.
                }                
            }
            else
            {
                cur=cur->next; //不等的话!!! 给的链表的指针本来是正确的,所以不用修改,只需移动cur到									//下一个节点.
            }
        }
        return dummy->next;
    }
};

思路

首先,链表题常用的方法是最前面加一个头节点,但是没有值.

其次,这种题要知道链表都是建好的.

cur一直指向的是链表中确定存在的值.这点很重要,如果这个节点不存在,就把cur->next指向绕过这个节点,若这个节点存在,cur就指向这个节点.然后再判断后面的值.