程序员面试金典-面试题02.01-移除重复节点

Dear 丶 2022-12-27 11:30 207阅读 0赞

## 程序员面试金典-面试题02.01-移除重复节点 ##

本题目是一个双指针问题，保持一个指针不动，移动需要移除节点的指针。

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
    
    示例1:
    
     输入：[1, 2, 3, 3, 2, 1]
     输出：[1, 2, 3]
    示例2:
    
     输入：[1, 1, 1, 1, 2]
     输出：[1, 2]
    提示：
    
    链表长度在[0, 20000]范围内。
    链表元素在[0, 20000]范围内。
    进阶：
    
    如果不得使用临时缓冲区，该怎么解决？
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/remove-duplicate-node-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

有两个关键点：  
1.使用数组记录节点是否重复；  
2.双指针操作

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    
    
    struct ListNode* removeDuplicateNodes(struct ListNode* head){
        
        if(head==NULL)
            return head;
        int data[20001];
        for(int i=0;i<20001;i++)
            data[i]=0;
        struct ListNode * ptr = head;
        while(ptr!=NULL)
        {
        
            int t = ptr->val;
            data[t]++;
            ptr = ptr->next;
        }
        ptr=head;
        struct ListNode * ptr_next=ptr;                //need double pointer
        while(ptr_next!=NULL)
        {
        
            int t = ptr->val;
            data[t]=-1;
            ptr_next = ptr_next->next;
            while(ptr_next != NULL && data[ptr_next->val]<0)
            {
        
                ptr_next=ptr_next->next;
            }
            ptr->next=ptr_next;
            ptr=ptr->next;
        }
        return head;
    }