1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 35 题] “复杂链表的复制”做题记录

[剑指 Offer 第 2 版第 35 题] “复杂链表的复制”做题记录

第 35 题:复杂链表的复制

传送门:复杂链表的复刻牛客网 online judge 地址

请实现一个函数可以复制一个复杂链表。

在复杂链表中,每个结点除了有一个指针指向下一个结点外,还有一个额外的指针指向链表中的任意结点或者 null 。

分析:一些细节要考虑到,特别是空结点的判断,以下两种方法都要遍历链表一遍以上,即遍历链表一遍是不够的。

思路1:有点巧妙,穿针引线,新旧断开。

Python 代码:

  class ListNode(object):
        def __init__(self, x):
            self.val = x
            self.next = None
            self.random = None


    class Solution(object):
        def copyRandomList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if head is None:
                return None

            # 第 1 步:根据 next 指针复制出一个新旧合一的链表
            cur_node = head
            while cur_node:
                # 先暂存 cur_node 的 next_node 下一次遍历要用
                next_node = cur_node.next

                new_node = ListNode(cur_node.val)

                cur_node.next = new_node
                new_node.next = next_node
                # 指针遍历到下一个结点
                cur_node = next_node
            # 第 2 步:根据旧结点 random 指针,给新结点的 random 指针做出正确的指向
            cur_node = head
            while cur_node:
                new_node = cur_node.next
                # 同样要先暂存 cur_node.next_node
                next_node = new_node.next
                # 要记得做非空判断,因为题目中说了 random 有可能为空
                new_node.random = cur_node.random.next if cur_node.random else None
                cur_node = next_node

            # 第 3 步:旧结点和新结点分离(拆分链表)
            cur_node = head
            res = cur_node.next
            while cur_node:
                new_node = cur_node.next
                # 同样要先暂存下一个结点
                next_node = new_node.next
                # 恢复原始结点
                cur_node.next = new_node.next
                # 恢复拷贝结点
                # 这里也要同样注意空指针的问题,克隆结点的最后一个结点的下一个结点是 null
                new_node.next = next_node.next if next_node else None
                cur_node = next_node
            return res

Java 代码:

  class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }

    public class Solution {
        public RandomListNode Clone(RandomListNode pHead) {
            // 极端情况,一定要写先出来
            if (pHead == null) {
                return null;
            }

            RandomListNode curNode = pHead;
            // 第 1 步:根据 next 指针复制出一个新旧合一的链表
            // 此时,奇数索引(从 1 开始计算)的结点是旧的结点,偶数索引的结点是新的结点
            RandomListNode nextNode;
            RandomListNode copyNode;
            while (curNode != null) {
                nextNode = curNode.next;
                copyNode = new RandomListNode(curNode.label);
                curNode.next = copyNode;
                copyNode.next = nextNode;
                curNode = nextNode;
            }

            // 第 2 步:根据旧结点 random 指针,给新结点的 random 指针做出正确的指向
            // 指针复位到起始结点
            curNode = pHead;
            while (curNode != null) {
                copyNode = curNode.next;
                nextNode = copyNode.next;
                // 特别注意
                // 特别注意
                // 特别注意:有的结点很可能 random 的指向为空(题目中明确说明)
                // 所以:只要遇到 next 引用的时候,一定要注意判断是否为空
                copyNode.random = curNode.random == null ? null : curNode.random.next;
                curNode = nextNode;
            }

            // 第 3 步:旧结点和新结点分离(拆分链表)
            curNode = pHead;
            RandomListNode res = pHead.next;
            while (curNode != null) {
                copyNode = curNode.next;
                nextNode = copyNode.next;
                // 恢复原始结点
                curNode.next = copyNode.next;
                // 恢复拷贝结点
                // 这里也要同样注意空指针的问题,克隆结点的最后一个结点的下一个结点是 null
                copyNode.next = copyNode.next == null ? null : copyNode.next.next;
                curNode = nextNode;
            }
            return res;
        }
    }

C++ 写法:

liwei2019101111_1.png

Java 版本里面还有一个网友的写法。

思路2:使用哈希表,复制出随机访问的指针。

Python 代码:

  class ListNode(object):
        def __init__(self, x):
            self.val = x
            self.next = None
            self.random = None


    class Solution(object):
        def copyRandomList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if head is None:
                return None
            map = dict()
            dummy_node = ListNode(-1)
            # p 指针用于新链表的 next 指针赋值
            p = dummy_node

            # 遍历一次链表,做两件事
            # 1、复制结点
            # 2、只管 next 指针
            cur_node = head
            while cur_node:
                new_node = ListNode(cur_node.val)
                # 把新旧结点的对应关系放在一个 map 里
                map[cur_node] = new_node
                cur_node = cur_node.next

                p.next = new_node
                p = new_node

            # 接下来做随机指针的复制
            for old_node, new_node in map.items():
                # 要记得判断是否为空,否则 None 不能作为 map  key
                if old_node.random:
                    new_node.random = map[old_node.random]
            return dummy_node.next

Java 代码:

  public class Solution3 {
        public RandomListNode Clone(RandomListNode pHead) {
            Map<RandomListNode, RandomListNode> map = new HashMap<>();
            RandomListNode curNode = pHead;
            // 体会这里设置虚拟头结点的必要性
            RandomListNode dummyNode = new RandomListNode(-1);
            RandomListNode p = dummyNode;
            // 完成复制 next 结点,并且将对应关系放入 Hash 表
            while (curNode != null) {
                RandomListNode newNode = new RandomListNode(curNode.label);
                map.put(curNode, newNode);
                curNode = curNode.next;
                p.next = newNode;
                p = newNode;
            }
            // 完成复制链表的 random 指针的赋值
            Set<Map.Entry<RandomListNode, RandomListNode>> entrySet = map.entrySet();
            for (Map.Entry<RandomListNode, RandomListNode> entry : entrySet) {
                entry.getValue().random = map.get(entry.getKey().random);
            }
            return dummyNode.next;
        }
    }

Java 代码:特别注意:在复制“指针”的时候,对空对象的判定,画图是十分关键的。

  class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }

    public class Solution {
        public RandomListNode Clone(RandomListNode pHead) {
            // 极端情况,一定要写先出来
            if (pHead == null) {
                return null;
            }

            RandomListNode curNode = pHead;
            // 第 1 步:根据 next 指针复制出一个新旧合一的链表
            // 此时,奇数索引(从 1 开始计算)的结点是旧的结点,偶数索引的结点是新的结点
            RandomListNode nextNode;
            RandomListNode copyNode;
            while (curNode != null) {
                nextNode = curNode.next;
                copyNode = new RandomListNode(curNode.label);
                curNode.next = copyNode;
                copyNode.next = nextNode;
                curNode = nextNode;
            }

            // 第 2 步:根据旧结点 random 指针,给新结点的 random 指针做出正确的指向
            // 指针复位到起始结点
            curNode = pHead;
            while (curNode != null) {
                copyNode = curNode.next;
                nextNode = copyNode.next;
                // 特别注意
                // 特别注意
                // 特别注意:有的结点很可能 random 的指向为空(题目中明确说明)
                // 所以:只要遇到 next 引用的时候,一定要注意判断是否为空
                copyNode.random = curNode.random == null ? null : curNode.random.next;
                curNode = nextNode;
            }

            // 第 3 步:旧结点和新结点分离(拆分链表)
            curNode = pHead;
            RandomListNode res = pHead.next;
            while (curNode != null) {
                copyNode = curNode.next;
                nextNode = copyNode.next;
                // 恢复原始结点
                curNode.next = copyNode.next;
                // 恢复拷贝结点
                // 这里也要同样注意空指针的问题,克隆结点的最后一个结点的下一个结点是 null
                copyNode.next = copyNode.next == null ? null : copyNode.next.next;
                curNode = nextNode;
            }
            return res;
        }
    }

Java 代码:

  import java.util.HashMap;
    import java.util.Map;
    import java.util.Set;

    /**
     * 使用 Hash 表的方式
     *
     * @author liwei
     */
    public class Solution2 {
        public RandomListNode Clone(RandomListNode pHead) {
            Map<RandomListNode, RandomListNode> map = new HashMap<>();
            RandomListNode curNode = pHead;
            // 体会这里设置虚拟头结点的必要性
            RandomListNode dummyNode = new RandomListNode(-1);
            RandomListNode p = dummyNode;
            // 完成复制 next 结点,并且将对应关系放入 Hash 表
            while (curNode != null) {
                RandomListNode newNode = new RandomListNode(curNode.label);
                map.put(curNode, newNode);
                curNode = curNode.next;
                p.next = newNode;
                p = newNode;
            }
            // 完成复制链表的 random 指针的赋值
            Set<Map.Entry<RandomListNode, RandomListNode>> entrySet = map.entrySet();
            for (Map.Entry<RandomListNode, RandomListNode> entry : entrySet) {
                entry.getValue().random = map.get(entry.getKey().random);
            }
            return dummyNode.next;
        }
    }

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 35 题] “复杂链表的复制”做题记录

链接:https://www.javajike.com/article/3282.html

« [剑指 Offer 第 2 版第 34 题] “二叉树中和为某一值的路径”做题记录
[剑指 Offer 第 2 版第 36 题] “二叉搜索树与双向链表”做题记录»

相关推荐

QR code