56.删除链表中重复的结点.md

56.删除链表中重复的结点

题目描述

• 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

 

解题思路

• 思路一，迭代。注意题目中说的是排序的链表，并且只要该元素重复出现就把所有包含该元素的结点都删除，而且最后要求返回链表头指针。首先处理链表头，如果相同的话全部删除然后继续往后找，直到确定头结点为止，然后再继续处理后面的；也可以直接按后面的方式处理，只不过每次删除一段结点之前要先判断一下删除的是不是头结点，代码更简洁，但会增加少许开销；或者也可以在前面新增一个头结点，然后后续就把新的头结点当作pre结点按照下面的方法统一处理即可，代码中用的这个方法。

  后面的部分需要两个指针，前一个不同元素结点指针pre，后续指针last，检查last结点是否和后面的元素相同，如果相同的话就把last指针一直向后移动直到不再相同，然后把pre指针的结点的next指针指向last的后一个结点，last移到后一个结点，删除中间无用结点（需要先把无用结点的开头地址保存起来），继续循环；如果last和后一个结点不同的话，就pre和last都向后移动，结合代码看比较容易理解。

• 思路二，递归，不推荐。该方法返回从当前输入结点开始，经过题目要求的处理以后的链表头结点。如果当前输入的头结点和后一个结点值相同，则一直向后查找到一个不相同的结点，返回以该结点作为输入进行递归的结果；如果当前头结点和后一个结点不同，则将头结点的next指向后从一个结点开始递归的结果。

 

代码

• 思路一，迭代。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead==NULL || pHead->next==NULL) return pHead;
        
        ListNode newHead(0);
        newHead.next = pHead;
        
        ListNode *pre=&newHead, *last=pHead;
        while(last != NULL){
            if(last->next && last->val==last->next->val){
                last = last->next; // while的条件和外面的if条件相同，加上这一句可以减少一次判断，不加也行
                while(last->next && last->val==last->next->val) last = last->next;
                ListNode* pDelete = pre->next;  // 用于删除无用结点
                pre->next = last->next;
                last = last->next;
                // 删除无用结点，要求不高的话也可以不删除
                while(pDelete!=last){
                    ListNode* temp = pDelete->next;
                    delete(pDelete);
                    pDelete = temp;
                }
            }
            else{
                pre = last;
                last = last->next;
            }
        }
        return newHead.next;
    }
};

• 思路二，递归，不推荐。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead==NULL || pHead->next==NULL) return pHead;
        
        if(pHead->val == pHead->next->val){
            while(pHead->next && pHead->val == pHead->next->val) pHead = pHead->next;
            return deleteDuplication(pHead->next);
        }
        else{
            pHead->next = deleteDuplication(pHead->next);
            return pHead;
        }
    }
};