剑指offer＜数据结构＞---------------链表

删除链表的重复节点

题目来源：牛客网

1、问题描述

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

数据范围：链表长度满足 0 \le n \le 1000 \ 0≤n≤1000 ，链表中的值满足 1 \le val \le 1000 \ 1≤val≤1000

进阶：空间复杂度 O(n)\ O(n) ，时间复杂度 O(n) \ O(n)

例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：

2、思路解析

思路：哨兵位+哈希
重复节点可能包括头节点、普通节点和尾节点，为了防止删除头节点而失去后边节点的地址所以给链表前边加一个哨兵位，删除头节点后将头节点下一个节点链接到哨兵位处，还有先遍历一遍链表将相同节点出现次数存入到哈希，结点值充当键值，出现次数充当values。后边遍历一次，判断出现次数，出现次数大于一的直接删除，直到遍历完链表为止

3、代码实现

/*
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;
        }
        //增加烧饼为
        ListNode*root= new ListNode(-1);
        root->next=pHead;
        ListNode*node=root->next;
        unordered_map<int,int> mp;
        while(node){
            mp[node->val]++;
            node=node->next;
        }
        ListNode*node1=root->next;
        ListNode*cur=root;
        while(node1){
            if(mp[node1->val]>1){
            while(node1&&mp[node1->val]>1){
                //出现次数大于1
                //删除节点
                ListNode *next=node1->next;
                cur->next=next;
                node1=next;
            }
            }else{
                cur=node1;
                node1=node1->next;
            }
            
        }
        return root->next;
    }
};

复杂链表的复制

题目来源：牛客网

1、问题描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

2、思路解析

思路：哈希表
普通链表的复制比较简单，但是这里的链表带了随机指针，指向随机一个节点，所以在一边遍历完想要复制完链表是无法做到的。所以这里借助map将每个节点的随即节点的对应的值存储在map充当键值，当前节点充当values，因为当前节点的随节点在后边还没有复制，所以还需要当前节点。步骤如下
（1）创建新链表的哨兵位，创建可变节点指向哨兵位置
（2）遍历链表 创建节点，将新节点链表新链表的后边
（3）判断当前节点是不是哪一个节点的随即节点，如果是就将values中的节点的随机指针指向当前节点
（4）将当前节点随机节点和当前节点插入到mp中
（5）在插入随机节点要注意随即节点判断是不是NULL

3、代码实现

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(pHead==NULL){
            return NULL;
        }
        int flag=1;
        //<当前节点，指向节点>
     unordered_map<int,RandomListNode*>mp;
         //先将指向节点节点充当键值，当前节点充当values
         //遍历节点如果等于当前节点在map中存在，就连接当前节点到values节点
         RandomListNode*proot=new RandomListNode(-1);//哨兵为
        RandomListNode*root=proot;
        while(pHead){
            //先构造节点
            root->next=new RandomListNode(pHead->label);
            root=root->next;
            //查找当前节点是不是在map中存在
            if(mp.count(pHead->label)){
                //存在,链接节点
                mp[pHead->label]->random=root;
            }
            
            //将随机节点和当前节点存入到map中
            //当前节点充当values
            
            //随即节点为NULL
            if(pHead->random!=NULL){
            mp[pHead->random->label]=root;
            }
            
            
            //更新节点
            pHead=pHead->next;
        }
        
        
        //前边没有链接随机节点      链接随即节点
        RandomListNode*root1=proot;
        while(root1){
            if(mp.count(root1->label)){
                //存在,链接节点
                mp[root1->label]->random=root1;
            }
            root1=root1->next;
        }
        
        return proot->next;
    }
};