输入一个复杂链表返回的结果是复制后复杂链表的headJava如何实现?下面一起来具体的了解一下实现方式及思想吧。

题目：

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

思路1：

一、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面;

二、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;

三、拆分链表，将链表拆分为原链表和复制后的链表

代码实现：

public class Solution
{
    public RandomListNode Clone(RandomListNode pHead)
    {
        if (pHead == null)
        {
            return null;
        }
        RandomListNode currentNode = pHead;
        //1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
        while (currentNode != null)
        {
            RandomListNode cloneNode = new RandomListNode(currentNode.label);
            RandomListNode nextNode = currentNode.next;
            currentNode.next = cloneNode;
            cloneNode.next = nextNode;
            currentNode = nextNode;
        }
        currentNode = pHead;
        //2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
        while (currentNode != null)
        {
            currentNode.next.random = currentNode.random == null ? null : currentNode.random.next;
            currentNode = currentNode.next.next;
        }
        //3、拆分链表，将链表拆分为原链表和复制后的链表
        currentNode = pHead;
        RandomListNode pCloneHead = pHead.next;
        while (currentNode != null)
        {
            RandomListNode cloneNode = currentNode.next;
            currentNode.next = cloneNode.next;
            cloneNode.next = cloneNode.next == null ? null : cloneNode.next.next;
            currentNode = currentNode.next;
        }
        return pCloneHead;
    }
}

思路2：

JAVA使用哈希表，时间复杂度O(N)，额外空间复杂度O(N)

代码实现：

import java.util.HashMap;
public class Solution
{
    public RandomListNode Clone(RandomListNode pHead)
    {
        HashMap < RandomListNode, RandomListNode > map = new HashMap < RandomListNode, RandomListNode > ();
        RandomListNode cur = pHead;
        while (cur != null)
        {
            map.put(cur, new RandomListNode(cur.label));
            cur = cur.next;
        }
        cur = pHead;
        while (cur != null)
        {
            map.get(cur)
                .next = map.get(cur.next);
            cur = cur.next;
        }
        RandomListNode resHead = map.get(pHead);
        cur = pHead;
        while (cur != null)
        {
            map.get(cur)
                .random = map.get(cur.random);
            cur = cur.next;
        }
        return resHead;
    }
}

思路3

代码实现：

class Solution
{
    public:
        /*
            1、复制每个节点，如：复制节点A得到A1，将A1插入节点A后面
            2、遍历链表，A1->random = A->random->next;
            3、将链表拆分成原链表和复制后的链表
        */
        RandomListNode * Clone(RandomListNode * pHead)
        {
            if (!pHead) return NULL;
            RandomListNode * currNode = pHead;
            while (currNode)
            {
                RandomListNode * node = new RandomListNode(currNode - > label);
                node - > next = currNode - > next;
                currNode - > next = node;
                currNode = node - > next;
            }
            currNode = pHead;
            while (currNode)
            {
                RandomListNode * node = currNode - > next;
                if (currNode - > random)
                {
                    node - > random = currNode - > random - > next;
                }
                currNode = node - > next;
            }
            //拆分
            RandomListNode * pCloneHead = pHead - > next;
            RandomListNode * tmp;
            currNode = pHead;
            while (currNode - > next)
            {
                tmp = currNode - > next;
                currNode - > next = tmp - > next;
                currNode = tmp;
            }
            return pCloneHead;
        }
};

复杂链表的复制Java实现及思路你掌握了吗?自己是否有好的思路了呢?请继续关注本站，有更多优质的Java实例可以分享给大家。