首页 > 代码库 > 复杂链表的复制

复杂链表的复制

2024-09-13 03:23:28   214人阅读

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

分析

如下图所示，先将每个节点复制后，放到该节点后面，完成复制后，再拆分。

技术分享

代码

/** * Created by wuchao on 17-3-29. *//*public class RandomListNode {    int label;    RandomListNode next = null;    RandomListNode random = null;    RandomListNode(int label) {        this.label = label;    }}*/public class test {    public static void main(String[] args){        RandomListNode node1 = new RandomListNode(1);        RandomListNode node2 = new RandomListNode(2);        RandomListNode node3 = new RandomListNode(3);        RandomListNode node4 = new RandomListNode(4);        RandomListNode node5 = new RandomListNode(5);        node1.next=node2;        node2.next=node3;        node3.next=node4;        node4.next=node5;        node1.random=node4;        node3.random=node1;        show(node1);        RandomListNode node = Clone(node1);        show(node1);        //show(node);    }    public static void show(RandomListNode node){        RandomListNode tmp = node;        while(tmp!=null){            System.out.print("{值:"+tmp.label+", 对象ID:"+tmp+", randomID:"+tmp.random+"}   ");            tmp=tmp.next;        }        System.out.println();    }    //以下为复制复杂链表的函数    public static RandomListNode Clone(RandomListNode pHead)    {        if(pHead==null) return null;        RandomListNode nodeTemp = pHead;        //先复制节点的值label        while(nodeTemp!=null){            RandomListNode nodeTemp2 = nodeTemp.next;            RandomListNode node = new RandomListNode(nodeTemp.label);            node.next=nodeTemp2;            nodeTemp.next=node;            nodeTemp = node.next;        }        //接着复制节点的random        nodeTemp = pHead;        while(nodeTemp!=null){            if(nodeTemp.random!=null){                nodeTemp.next.random=nodeTemp.random.next;            }            nodeTemp=nodeTemp.next.next;        }        //show(pHead);        //拆分，拆分时注意还原pHead链表，因为pHead链表已经被修改        RandomListNode head = pHead.next;        RandomListNode temp1 = head;        RandomListNode temp2 = pHead;        while(temp1.next!=null){            temp2.next = temp2.next.next;            temp2 = temp2.next;            temp1.next = temp1.next.next;            temp1=temp1.next;        }        temp2.next=null;        return head;    }}

 

复杂链表的复制


联系
我们