NC24 题解 | #删除有序链表中重复的元素-II#

题意分析

给出一个链表，要求我们返回这个链表中的所有的元素，但是与NC25不同的是，要求这些元素是在初始的链表里面只出现一次的元素，同时这个链表的所有的元素需要保持原来的相对位置关系。这个就不是去重了。

思路分析

我们思考，如何把出现多次的元素在链表里面去掉呢？
- 方法还是利用哈希进行处理，我们用一个哈希表统计这个链表里面的所有的元素出现的次数。处理完之后我们就直到哪些元素需要保留了。
其次，我们如何保持原来的顺序呢？
- 保持原来的顺序就要我们按照链表的顺序进行访问。其实这里可以自己重新定义一些新的变量，构造出一个完完全全的新的链表。但是其实没有必要，这样对内存的浪费是很大的。其实我们可以在原来的基础上进行处理，我们只要把一些指针的next指针重新指定就行了。这里我定义了一个pre，用来处理返回答案的那条链表此时所指向的位置，然后用一个now用来进行遍历初始的链表。一旦遇到合适的结点，我就将这个pre指针的next指针指向这个结点，同时pre更新为now，依次下去。但是最后要注意的是我们需要将pre->next置为NULL。确保链表正常终止。但是这个和NC25有点不一样的就是我们的头节点需要我们进行寻找，可能不是初始链表的头节点。这里可能找不到，所以我们直接返回空即可。其次，找到之后就是按照NC25的思路进行查找，和上面的思路一样。

具体更新链表请看下面的图进行理解（请原谅我用的是和那题一样的图，因为思路都是一样的，就是处理有点不一样）

图片说明

那么，答题的思路就是我们先进行哈希将这些出现多次的结点排除，然后再进行一次遍历，操作和之前的一样。最后就可以得到最终的链表了。

写法一 C++版

代码如下
- 我们只需要对链表进行遍历，所以时间复杂度为O(N)
- 我们需要利用哈希表存储整个链表的所有的元素，所以空间复杂度为O(N)

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        // 特判链表为空的情况，防止出现段错误
        if(head==NULL){
            return head;
        }
        unordered_map<int,int> mp;
        ListNode* now=head;
        // 先对链表进行一次遍历哈希出每个数字出现的次数
        while(now){
            mp[now->val]++;
            now=now->next;
        }

        now=head;
        // 找到可以作为头节点的第一个结点指针
        while(now){
            if(mp[now->val]==1){
                head=now;
                break;
            }
            now=now->next;
        }
        // 注意这里可能找不到，所以需要直接返回空
        if(now==NULL){
            return NULL;
        }
        ListNode* pre=now; // 找到了就用一个pr先存着
        now=now->next;
        // now开始向后面进行遍历
        while(now){
            // 如果这个数字出现过
            if(mp[now->val]==1){
                pre->next=now;
                pre=now;
            }
            now=now->next;
        }
        // 最后记得结尾指向null
        pre->next=NULL;
        return head;
    }
};

写法二 Go语言版

代码如下
- 我们只需要对链表进行遍历，所以时间复杂度为O(N)
- 我们需要利用哈希表存储整个链表的所有的元素，所以空间复杂度为O(N)

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @return ListNode类
*/
func deleteDuplicates( head *ListNode ) *ListNode {
    // write code here
    if(head==nil){
        return nil
    }
    pre := new(ListNode)
    now := new(ListNode)
    var mp map[int]int
    mp = make(map[int]int)
    now=head
     // 进行一次遍历找到出现多次的数字，排除相关的结点指针
    for{
        if(now==nil){
            break
        }
        mp[now.Val]+=1;
        now=now.Next
    }
    now=head
    // 再进行一次遍历找到头节点，注意不一定是初始链表的第一个节点
    for {
        if(now==nil){
            break
        }
        if(mp[now.Val]==1){
            pre=now
            break
        }
        now=now.Next
    }
    // 没有找到头节点，直接返回nil
    if(now==nil){
        return nil
    }
    head=pre // pre用来记录最终的链表的尾部结点
    now=now.Next
    for {
        if(now==nil){
            break
        }
        // 如果符合题目条件，只出现过一次，那么更新pre指针
        if(mp[now.Val]==1){
            pre.Next=now
            pre=now
        }
        now=now.Next
    }
    // 最后链表尾部指向nil
    pre.Next=nil
    return head
}