剑指offer系列之二十四:复杂链表的复制

题目描述

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点)。

下面是我第一想到的思路:因为next指针是固定的,在复制的时候这点比较好处理,由于特殊指针是任意的,可能是在节点之前,也可能在节点之后,所以必须解决这个棘手问题。不管至少,可以从链表的第一个节点开始遍历,直到该特殊指针指向的节点,并设置该节点的特殊指针。还有一种思路(也是书上的思路):第一步,复制原来链表的节点,并设置next指针,这一步不同于简单的复制节点,而是把每个复制的节点都链在原节点的后面,相当于复制节点之间隔了一个原节点;第二步,设置复制节点的特殊指针,由于在第一步左了特殊处理,所以当一个节点R的特殊指针指向节点N的时候,复制节点R’的特殊指针则是N’,这样就可以在O(1)时间定位到R的特殊指针指向的节点;第三步,从链表中抽取出复制节点,由于复制节点是间隔相连的,所以这一步比较好处理。综合以上三个步骤,就完成了复杂链表的复制。

下面是基于第二种思路的Java代码(已被牛客AC):

package com.rhwayfun.offer;

public class CopyComplicateLinkedList {

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

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

    public RandomListNode Clone(RandomListNode pHead) {
        CloneNodes(pHead);
        ConnectSiblingNodes(pHead);
        return ConnectFinalListNodes(pHead);
    }

    // 第一步:复制链表节点
    private void CloneNodes(RandomListNode pHead) {
        RandomListNode node = pHead;
        while (node != null) {
            RandomListNode cloneNode = new RandomListNode(node.label);
            cloneNode.next = node.next;
            cloneNode.random = null;

            node.next = cloneNode;
            node = cloneNode.next;
        }
    }

    // 第二步:设置每个节点的随机指针
    private void ConnectSiblingNodes(RandomListNode pHead) {
        RandomListNode node = pHead;
        while (node != null) {
            RandomListNode clone = node.next;
            if (node.random != null) {
                clone.random = node.random.next;
            }
            node = clone.next;
        }
    }

    // 第三步:组合复制的节点
    private RandomListNode ConnectFinalListNodes(RandomListNode pHead) {
        RandomListNode node = pHead;
        RandomListNode cloneHead = null;
        RandomListNode cloneNode = null;

        // 设置第一个节点
        if (node != null) {
            cloneHead = node.next;
            cloneNode = node.next;
            node.next = cloneNode.next;
            node = node.next;
        }

        while (node != null) {
            cloneNode.next = node.next;
            cloneNode = cloneNode.next;
            node.next = cloneNode.next;
            node = node.next;
        }
        return cloneHead;
    }

    public static void main(String[] args) {
        RandomListNode pHead = new RandomListNode(1);
        RandomListNode node1 = new RandomListNode(2);
        RandomListNode node2 = new RandomListNode(3);
        RandomListNode node3 = new RandomListNode(4);
        RandomListNode node4 = new RandomListNode(5);
        RandomListNode node5 = new RandomListNode(6);
        RandomListNode node6 = new RandomListNode(7);
        RandomListNode node7 = new RandomListNode(8);

        pHead.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;

        pHead.random = node4;
        node2.random = node6;

        @SuppressWarnings("unused")
        RandomListNode node = new CopyComplicateLinkedList().Clone(pHead);
        System.out.println(node);
    }
}
时间: 2024-09-23 17:27:00

剑指offer系列之二十四:复杂链表的复制的相关文章

剑指offer系列之二十六:输出字符串的全排列

题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列.例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba. 结果请按字母顺序输出. 输入描述: 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母. 此题与剑指offer原题存在一些初入,在原题中并没有规定字符串中字符是否有重复的出现.不过思路是一致的,只不过是添加额外的判断罢了.下面说说我的思路吧:先不考虑是否出现重读字符,要对一个字符进行全排列,可以

剑指offer系列之二十五:二叉搜索树与双向链表

题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表.要求不能创建任何新的结点,只能调整树中结点指针的指向. 由于二叉搜索树的中序遍历就是排序的,如果是构造单链表,只需要一次中序遍历就可以了,但现在需要构造双链表,也就是在中序遍历的过程中需要设置每个节点的left与right指针,现在问题是如何设置这两个指针?二叉搜索树有一个特点,就是根节点的左子树上所有节点都比根节点的值小,而右子树上的所有节点的值都比根节点的值大,利用这个性质,当遍历根节点的左孩子的时候,可以继续把其当做左子

剑指offer系列之二十二:二叉搜索树的后续遍历序列

题目描述 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果.如果是则输出Yes,否则输出No.假设输入的数组的任意两个数字都互不相同. 此题仍然是对二叉树遍历方法的考察,但是与直接对遍历方法的考察不太一样,因为这里的输入是后续遍历的序列,所以要判断该序列是否是某二叉树的后续遍历结果,关键在于找出根节点,根节点的左子树和根节点的右子树,然后继续对左子树和右子树进行判断,直到全部元素访问完毕.这里很显然是一个递归的过程.由于后续遍历是先访问双亲节点,接着访问左孩子,再访问右孩子,所以需

剑指offer系列之二十:栈的压入、弹出序列

题目描述 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序.假设压入栈的所有数字均不相等.例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列. 要判断一个序列是不是另一个序列的弹出序列,首先我们得知道栈的特点是FIFO,其次,由于压入序列是确定的(这里指的"确定"是说相对位置是确定的),就是说压入序列之间的元素可能会经历压入后马上被弹出的情况.具体思路是:

剑指offer系列之二十九:连续子数组的最大和

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学.今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决.但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止).你会不会被他忽悠住? 这实际上是一个逐步比较的过程,假设累加进行到某一步,继续累加下一个数的时候发现和变小了,就应该重新计算当前累加的

剑指offer系列之二十七:数组中出现次数超过一半的数

题目描述 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字.例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}.由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2.如果不存在则输出0. 思路分析:由于是一个数字,因为其次数超过1,那么其出现的出现综合肯定实际大于其他所有数字之和的.因为如此,我们可以设置一个变量用于辨识这个变量,遇到相同的数字就把次数增加1,如果没有没有遇到就把次数减少1,那么肯定次数有可能变为0,因为没有遇到相同的.因为那个数字的次数出现了超

剑指offer系列之二十一:从上到下打印二叉树

题目描述 从上往下打印出二叉树的每个节点,同层节点从左至右打印. 此题实际上就是二叉树层序遍历方法的考察,具体思路是:使用一个集合(或者栈,但是相对来说使用栈操作会方便一些)来保存遍历的节点,还需要创建一个集合用来保存最后输出的遍历序列.从根节点开始遍历,首先把该节点放入集合中,并输出其值,之后便从集合中移除该节点,不过在此之前需要判断该节点是否有左右孩子,如果有左右(满足其一就可以)孩子,便把左右孩子放入集合中.每次输出值后便把节点具体的值放入遍历集合中,作为最后的返回结果. 下面是基于这种思

剑指offer系列之二:字符串空格替换

题目描述: 请实现一个函数,将一个字符串中的空格替换成"%20".例如,当字符串为We Are Happy,则经过替换之后的字符串为We%20Are%20Happy. 看到这题,我的第一思路是这样的:一组单词不是有空格嘛,所以直接使用String类的split函数直接分割为char数组不就好了,不过在这之前需要判断一下第一个位置和最后一个位置是否有空格,然后针对空格的出现情况再进行替换.发现OJ的时候,如你所猜,自然是失败的.因为我忽略一个问题,就是如果一个句子中都是空格,调用spli

剑指offer系列之二十三:二叉树中和为某一值得所有路径

题目描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径. 由于是从根节点开始遍历的,所以自然联想到前序遍历,但是问题并没有那么简单,在遍历的过程中需要记录遍历的所有节点值的和,当某条路径遍历完毕之后,还需要切换到另一个节点,比如从某个节点的左孩子切换到右孩子,然后需要重新计算总和,并且需要减去原来那个节点的值.大概思路是:使用前序遍历的方式,如果遍历到叶子节点,和恰好是目标值,那么就将遍历经过的所有节点