【链表】剑指offer——面试题57：删除链表中重复的结点

牛客

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # write code here
        if not head or not head.next:
            return head
        l, r = head, head.next
        while l and r:
            if l.val != r.val:
                l, r = l.next, r.next
            else:
                while r and l.val == r.val:
                    r = r.next
                l.next = r
                l = l.next
                r = r.next if r else None

        return head

Java

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next; // 可能存在多个重复节点，所以暂且不动cur
            } else {
                cur = cur.next;
            }
        }

        return head;
    }
}

##Solution1:
删两遍，自己想的破算法。理论上时间复杂度也是$O(n)$，并非最优解。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) { //有序单链表，就是考察链表的删除操作，但是删两遍
        if(pHead == NULL)
            return NULL;
        struct ListNode *temp = pHead, *dupli_node;
        int duplication = pHead->val; //用来记录结点的数值，初始化为首结点的值
        set<int> vec_set;  //用来存放所有重复过的数值
        while(temp->next != NULL) { //第一遍删除
            if(temp->next->val != duplication) { //不重复的情况
                duplication = temp->next->val;
                temp = temp->next;
            }
            else { //该结点的值
                vec_set.insert(duplication);
                dupli_node = temp->next;
                temp->next = temp->next->next;
                free(dupli_node);
            }
        }
        
        while(vec_set.find(pHead->val) != vec_set.end()) { //先找到链表起点
            dupli_node = pHead;
            pHead = pHead->next;
            free(dupli_node);
            if (pHead == NULL)//如果链表表头为空，要及时判断返回
				return NULL;   //此时对应着链表中所有结点的值都相同的情况
        }
        
        temp = pHead;//从新起点遍历删除第二遍，新起点肯定是未重复过的
        while(temp->next != NULL) { //
            if(vec_set.find(temp->next->val) != vec_set.end()){
                dupli_node = temp->next;
                temp->next = temp->next->next;
                free(dupli_node);
            }
            else 
                temp = temp->next;
        }
        return pHead;
    }
};

##Solution2:
书上的思路。这种方法是把结点值重复的链表结点给踢掉了，并没有主动释放内存空间。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if (!pHead) return pHead;
        ListNode *pre = NULL; //指向前面最晚访问过的不重复结点
        ListNode *p = pHead; //指向当前处理的结点
        ListNode *q = NULL; //指向当前处理结点后面结点
        while (p) {
            //当前结点p，（其实是p指向当前结点），
            //与它下一个结点p->next的val相同，说明要删掉有这个val的所有结点
            if (p->next != NULL && p->next->val == p->val) {
                q = p->next;
                //找到q，它指向最后一个与p val相同的结点，那p 到 q （包含） 都是要删除的
                while (q != NULL && q->next != NULL && q->next->val == p->val) 
                    q = q->next;
                //如果p指向链表中第一个元素，p -> ... -> q ->... , 要删除p到q, 
                //将指向链表第一个元素的指针pHead指向q->next。
                if (p == pHead) {
                    pHead = q->next;
                } else //如果p不指向链表中第一个元素，pre -> p ->...->q ->... ，
                       //要删除p到q，即pre->next = q->next
                    pre->next = q->next;
                //当前处理的p要向链表尾部移动
                p = q->next;
            } else {
                pre = p;
                p = p->next;
            }
        }
        return pHead;
    }
};