题意分析

  • 给出一个链表，要求我们返回这个链表中的所有的元素，要求这些元素只出现一次，同时这个链表的所有的元素需要保持原来的相对位置关系。简单来说就是先去重，然后我们按照原来的位置关系重新构造这个链表返回即可。

思路分析

  • 我们思考，如果出现相同的数字我们如何去重呢？
    • 这里我是利用的map进行处理，存储这个数字出现的次数，如果出现超过一次，那么就直接在链表里面跳过。
  • 其次，我们如何保持原来的顺序呢？
    • 其实这里可以自己重新定义一些新的变量，构造出一个完完全全的新的链表。但是其实没有必要，这样对内存的浪费是很大的。其实我们可以在原来的基础上进行处理，我们只要把一些指针的next指针重新指定就行了。这里我定义了一个pre，用来处理返回答案的那条链表此时所指向的位置，然后用一个now用来进行遍历初始的链表。一旦遇到合适的结点，我就将这个pre指针的next指针指向这个结点，同时pre更新为now，依次下去。但是最后要注意的是我们需要将pre->next置为NULL。确保链表正常终止。
  • 具体请看下面的图进行理解

图片说明

写法一 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
        unordered_map<int,bool> mp;
        // 特判为空的情况，防止段错误
        if(head==NULL){
            return NULL;
        }
        ListNode* now=head;
        mp[now->val]=true;  // 先处理第一个结点，第一个结点一定是头节点
        ListNode* pre=now;  // now是用来存储遍历的时候的中间结点的
        now=now->next;
        // 不断对链表进行循环遍历
        while(now){
            // 如果这个结点对应的值出现过，直接跳过
            if(mp[now->val]){
                now=now->next;
            }else{
                // 将pre的next指针指向这个结点，同时更新pre
                pre->next=now;
                pre=now;
                mp[now->val]=true;  // 标记为访问过
                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用来记录最终链表的尾部结点
    pre := new(ListNode)
    // now用来记录遍历初始链表的结点
    now := new(ListNode)
    var mp map[int]bool
    mp = make(map[int]bool)
    pre=head;
    mp[pre.Val]=true
    now=head;
    now=now.Next
    for{
        // 到了链表尾部
        if(now==nil){
            break
        }
        // 如果被访问过直接跳过
        if(mp[now.Val]==true){
            now=now.Next
        }else{
            // 将pre.Next更新为now
            pre.Next=now
            pre=now
            mp[now.Val]=true  // 标记为访问过
            now=now.Next
        }
    }
    // 最后将尾部指针指向nil
    pre.Next=nil
    return head;
}