[TOC]

​ 本文主要记录链表的相交、合并、排序的相关LeetCode题目的实现代码，直接给出本文各个题目的答案，供有需求的读者学习或复制。

一、链表复制

138. 复制带随机指针的链表（中等难度）

剑指 Offer 35. 复杂链表的复制（中等难度）

class Solution {
public:
    /*难点：random可能指向未创建的节点*/
    Node* copyRandomList(Node* head) {
        if(head==NULL) return NULL;
        // 第一步：遍历原始链表，创建新节点并且存入哈希表中
        unordered_map<Node*,Node*> dict;//key:原有链表节点 value:新创建链表节点
        Node* cur=head;
        while(cur){
            dict[cur]=new Node(cur->val);//存入哈希表
            cur=cur->next;
        }
        // 第二步：遍历原始链表，修改哈希表中每个新节点的next指针和random指针
        cur=head;
        while(cur){
            Node* curNewNode=dict[cur];// 获取当前节点对应的新节点
            curNewNode->next=dict[cur->next];// 修改新节点的next指针
            curNewNode->random=dict[cur->random]; // 修改新节点的random指针
            // 循环前进
            cur=cur->next;
        }
        return dict[head];
    }
};

二、链表与二叉树

剑指 Offer 36. 二叉搜索树与双向链表（中等难度）

426. 将二叉搜索树转化为排序的双向链表（中等难度）

class Solution {
private:
    Node* pre=NULL; // 当前访问节点的前一个节点
    Node* head=NULL;// 双向循环链表的头结点
public:
    Node* treeToDoublyList(Node* root) {
        if(root==NULL) return NULL;
        // 采用中序遍历的方式遍历二叉搜索树，修改为双向链表
        dfs(root);
        // 修改为循环链表
        head->left = pre;//头结点指向尾结点
        pre->right = head;//尾结点指向头结点
        return head;
    }
    // 中序遍历
    void dfs(Node* cur){
        // 终止条件
        if(cur==NULL) return;
        // 递归左节点 
        dfs(cur->left);
        // 处理节点head,pre,cur
        if(pre) pre->right=cur;// 如果pre不为空，说明双向链表上已经有节点，其指向当前节点
        else head=cur;// 如果pre为空，说明双向链表没有节点，设置头结点
        cur->left=pre;// 当前节点指向上一个
        pre=cur;// 更新上一个节点
        // 递归右节点
        dfs(cur->right);
    }
};

109. 有序链表转换二叉搜索树（中等难度）

class Solution {
public:
    // 在[left,right)获取中间节点
    ListNode* getMid(ListNode* left, ListNode* right) {
        ListNode* fast = left;
        ListNode* slow = left;
        while (fast != right && fast->next != right) {
            fast = fast->next->next;// 前进2步
            slow = slow->next;// 前进1步
        }
        return slow;
    }
    // 在[left,right)中序遍历构建二叉搜索树
    TreeNode* buildTree(ListNode* left, ListNode* right) {
        if (left == right) return nullptr;
        // 构建中间节点
        ListNode* mid = getMid(left, right);// 获取中间节点
        TreeNode* root = new TreeNode(mid->val);//构建根节点
        // 递归左右节点
        root->left =  buildTree(left, mid);
        root->right = buildTree(mid->next, right);
        return root;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        return buildTree(head, nullptr);
    }
};

114. 二叉树展开为链表（中等难度）

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        // 快指针每次走2步，慢指针每次走1步，相遇即有环
        while(fast  && fast->next ) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，说明有环
            if (slow == fast) {
                slow=head;
                // head和相遇点相同速度出发再次相遇的就是入口
                while(fast&& slow) {
                    // 快慢指针第一次相遇，说明此时为入口
                    if (slow == fast) return slow;;
                    slow = slow->next;
                    fast = fast->next;
                }
            }
        }
        return NULL;
    }
};