剑指Offer 26 复杂链表的复制

题目描述

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

思路

方法一：map关联
首先我们就是创建一个新的结点，然后就next，next这样复制；等于把原链表不包括随机访问的部分都复制了，那么问题来了，如何复制random呢？我们在复制next的时候，将原表与新表建立hash表；这样复制出的结点可以通过hashmap，找到旧结点的random；

代码

static public RandomListNode mapclone(RandomListNode pHead)
    {
        if (pHead ==null)
            return  null;
        Map<RandomListNode,RandomListNode> m=new HashMap<>();               //建立hashmap
        RandomListNode head1 = pHead;                                       //head1是原表结点
        RandomListNode head2 = new RandomListNode(head1.label);             //head2是新表结点
        RandomListNode newhead = head2;                                     //保留一下新表的头结点
        m.put(head1,head2);                                                 //建立hash映射
        while (head1!=null)
        {
            if (head1.next!=null)
                head2.next = new RandomListNode(head1.next.label);          //复制结点
            else
                head2.next = null;
            head1 = head1.next;                                             //向后移动
            head2 = head2.next;
            m.put(head1,head2);                                             //放进hash表
        }
        head1 = pHead;
        head2 = newhead;
        while (head1!=null)
        {
            head2.random =m.get(head1.random);                              //通过hash表查询random
            head1 = head1.next;
            head2 = head2.next;
        }
        return  newhead;
    }

方法二：三步法

这里写图片描述

代码

```java
static public RandomListNode Clone(RandomListNode pHead)
{
if (pHead==null)
return null;
clone(pHead);
connect(pHead);

    return reconnect(pHead);
}

static  public  void clone(RandomListNode head)     //在每一个节点后面加一个克隆节点
{
    RandomListNode node = head;
    while (node!=null)
    {
        RandomListNode clone = new RandomListNode(node.label);  //克隆结点
        clone.next=node.next;
        clone.random=null;

        node.next=clone;                                        //node.next指向克隆结点
        node=clone.next;                                        //下一个结点
    }
}

static  public  void  connect(RandomListNode head)
{
    RandomListNode node = head;
    while (node!=null)
    {
        if (node.random!=null)                  //random的复制
        {
            node.next.random = node.random;
        }
            node = node.next.next;

    }
}
static  public  RandomListNode  reconnect(RandomListNode head)
{
    RandomListNode clonehead = head.next;           //保留一下克隆结点的头结点

    RandomListNode clone = head;                   
    RandomListNode node=head;
    /*
    进行结点分离
     */
    if (node!=null)                                 
    {
        clone = node.next;
        node.next=clone.next;
        node = node.next;
    }
    while (node!=null)                          
    {
        clone.next = node.next;
        clone = clone.next;
        node.next =clone.next;
        node = node.next;
    }

    return clonehead;
}

收获

hashmap的使用，稍微还是用了一下的嘛；
一定要注意空指针；注意对null的处理
关于指针的操作只看代码很难弄懂，还是动手敲一下吧；

2017-03-26