《剑指offer》面试题35. 复杂链表的复制

问题描述

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]

输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]

输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = []

输出：[]

解释：给定的链表为空（空指针），因此返回 null。

提示：

-10000 <= Node.val <= 10000

Node.random 为空（null）或指向链表中的节点。

节点数目不超过 1000 。

问题分析

分为以下三个步骤：

在原链表的每个节点后面拷贝出一个新的节点。
依次给新的节点的随机指针赋值，而且这个赋值非常容易 cur->next->random = cur->random->next。
断开链表可得到深度拷贝后的新链表。

举个例子来说吧，比如原链表是 1(NULL) -> 2(1) -> 3(NULL) -> 4(3)，括号中是其 random 指针指向的结点，那么这个解法是首先比遍历一遍原链表，在每个结点后拷贝一个同样的结点，但是拷贝结点的 random 指针仍为空，则原链表变为 1(NULL) -> 1(null) -> 2(1) -> 2(null) -> 3(NULL) -> 3(NULL) -> 4(2) ->4(NULL)。然后第二次遍历，是将拷贝结点的 random 指针赋上正确的值，则原链表变为 1(NULL) -> 1(NULL) -> 2(1) -> 2(1) -> 3(NULL) -> 3(NULL) -> 4(2) -> 4(2)，注意赋值语句为：cur->next->random = cur->random->next;这里的 cur 是原链表中结点，cur->next 则为拷贝链表的结点，cur->next->random 则为拷贝链表的 random 指针。cur->random 为原链表结点的 random 指针指向的结点，因为其指向的还是原链表的结点，所以我们要再加个 next，才能指向拷贝链表的结点。最后再遍历一次，就是要把原链表和拷贝链表断开即可

代码

/*

// Definition for a Node.

class Node {

public:

    int val;

    Node* next;

    Node* random;

    Node(int _val) {

        val = _val;

        next = NULL;

        random = NULL;

    }

};

*/

class Solution {

public:

    Node* copyRandomList(Node* head) {

       if(!head)return NULL;

       Node* cur = head;

       //将每个链表的节点后面都拷贝一个相同数值的节点,但拷贝节点的random为空

       while(cur)

       {

           Node* t = new Node(cur->val);

           t->next = cur->next;

           cur->next = t;

           cur = t->next;

       }

       cur = head;

       //对拷贝节点的random进行赋值

       while(cur)

       {

           if(cur->random)

              cur->next->random = cur->random->next;//实际上指向的是cur->random,这个是由cur->random拷贝出来的那一个

              cur = cur->next->next;

       }

       cur = head;

       //将拷贝的节点分离出来

       Node* ans = cur->next;

       Node* t  = ans;

       while(cur)

       {

           cur->next = cur->next->next;

           cur = cur->next;

           if(t->next)

           {

               t->next = t->next->next;

               t = t->next;

           }

       }

       return ans;

    }

};

结果

执行用时 :16 ms, 在所有 C++ 提交中击败了65.68%的用户

内存消耗 :11 MB, 在所有 C++ 提交中击败了100.00%的用户

当然还有递归和哈希表的解法，后面补充。

巴特西

《剑指offer》面试题35. 复杂链表的复制

问题描述

问题分析

代码

最新文章

热门文章