题目

• 在一个排序的链表中，存在重复的节点，请删除该链表中重复的节点，重复的节点不保留。
• 数据范围

• 链表中节点 val 值取值范围 [0,100]。

• 链表长度 [0,100]。

• 结点定义

  struct ListNode {

  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}

  };

示例

• 示例1

• 输入：1->2->3->3->4->4->5
• 输出：1->2->5

• 示例2

• 输入：1->1->1->2->3
• 输出：2->3

代码

解法：

class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        // 有可能删去头结点，定义假头结点简化代码
        auto dummy = new ListNode(0);
        dummy->next = head;
        
        auto p = dummy;
        auto q = p->next;
        
        
        while(p->next){
            while(q && p->next->val == q->val){
                q = q->next;
            }  
            if(p->next->next == q){
                p = p->next;
            }else{
                p->next = q;
            }
            
        }
        return dummy->next;
    }
};

代码分析：

auto dummy = new ListNode(0);
dummy->next = head;

因为有可能删去头结点，定义假头结点简化代码。接着看 while 里面：

while(q && p->next->val == q->val){
    q = q->next;
}

如果是重复的值，就让 q 一直往后走。

if(p->next->next == q){
    p = p->next;
}else{
    p->next = q;
}

如果 p->next->next == q说明 q 只走了一次，所以没有重复的，这时候 p 可以移到下一个结点。否则说明有重复的结点，p 直接移到 q 的位置即可。

题目：删除链表中重复的节点