[算法学习]复杂链表的复制

算法

问题描述： 复制一个复杂链表。 在复杂链表中，每个结点除了有一个指向下一个结点的next指针外，还有一个 sibing指针 指向链表中任意结点或者NULL。

解法一：“爆破”

解法分析：

  1. 遍历第一遍数组，把复制链的next和各结点值复制好。需要时间O(n)
  2. 第二遍遍历，二重for循环根据原链表，将复制链的slibing指针连接好。需要时间O(n^2)
  3. 需要时间复杂度是O(n^2)，空间复杂度是O(1)

参考代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
 * 复杂链表的结点
 *
 * @author kesar
 *
 */
static class Node
{
    int val;
    Node next;
    Node slibing;

    public Node(){}

    public Node(int val)
    {
        this.val = val;
    }

    @Override
    public String toString()
    {
        return "Node [val=" + val + "]";
    }
}

/**
 * 第一种解法：暴力复制。复制一遍next的，再每个结点遍历一遍进行slibing的比较。 时间复杂度是：O(n^2)，空间复杂度是：O(1)
 *
 * @param oHead
 * @return
 */
public static Node copy1(Node oHead)
{
    if (oHead == null)
    {
        return null;
    }
    // 复制的链表的头结点
    Node cHead = new Node(oHead.val);

    // oMove是原链表上遍历用的移动指针，cMove是复制链表上遍历用的移动指针
    // 复制Node结点的值以及next链关系
    for (Node oMove = oHead.next, cMove = cHead; oMove != null; cMove = cMove.next, oMove = oMove.next)
    {
        cMove.next = new Node(oMove.val);
    }

    // 复制slibing的链关系
    for (Node oMove = oHead, cMove = cHead; oMove != null; cMove = cMove.next, oMove = oMove.next)
    {
        if (oMove.slibing == null)
            continue;
        // 查找开始： 遍历查找slibing所指原链表结点对应在copy链表中的结点
        Node findNode = cHead;
        for (; findNode != null && findNode.val != oMove.slibing.val; findNode = findNode.next)
            ;
        // 查找结束：findNode就是结果
        cMove.slibing = findNode;
    }

    return cHead;
}

解法二：使用辅助空间

解法分析：

  1. 使用一个HashMap(Key：原链表上的结点，Value：复制链表上的结点)，空间复杂度是O(n)
  2. 遍历第一遍数组：每次创建复制链的结点时，需要先查找HashMap中结点是否存在，不存在才创建，然后保存结点到HashMap中。需要时间O(n)
  3. 需要时间复杂度是O(n)，空间复杂度是O(n)

参考代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * 第二种解法：利用HashMap的O(1)的高效率查找来取代第一中解法中的一个for循环。用O(n)的空间换来O(n)的时间。时间复杂度O(n)，空间复杂度：O(n)
 *
 * @param oHead
 * @return
 */
public static Node copy2(Node oHead)
{
    if (oHead == null)
    {
        return null;
    }
    // 辅助空间：Key：原链表上的结点，Value：复制链表上的结点
    HashMap<Node, Node> map = new HashMap<Node, Node>();

    // 初始化复制链表的头结点
    Node cHead = new Node(oHead.val);
    map.put(oHead, cHead);
    if (oHead.slibing != null)
    {
        cHead.slibing = new Node(oHead.slibing.val);
        map.put(oHead.slibing, cHead.slibing);
    }
    // 作用：遍历原链表，复制结点到复制链表中。
    // 思路是这样：先从map找原结点对应的复制结点，如果没找到，就创建一个，然后连接到复制链表中，然后put入map中，便于其他时候使用
    for (Node oMove = oHead.next, cMove = cHead; oMove != null; oMove = oMove.next, cMove = cMove.next)
    {
        if (map.containsKey(oMove))
        {
            cMove.next = map.get(oMove);
        }
        else
        {
            cMove.next = new Node(oMove.val);
            map.put(oMove, cMove.next);
        }
        Node slibing = oMove.slibing;
        if (slibing == null)
        {
            continue;
        }
        if (map.containsKey(slibing))
        {
            cMove.next.slibing = map.get(slibing);
        }
        else
        {
            cMove.next.slibing = new Node(slibing.val);
            map.put(slibing, cMove.next.slibing);
        }
    }
    return cHead;
}

解法三：“伸长分裂法”

解法分析：

  1. 遍历原链表。在原链表的每个结点的后面插入对应复制结点，将原链表“伸长”1倍；
  2. 遍历原链表。将复制结点的slibing连接好；
  3. 遍历原链表。将原结点和复制结点“分裂”开，将next连接好；
  4. 需要时间复杂度是O(n)，空间复杂度是O(1)

参考代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * @param oHead
 * @return
 */
public static Node copy3(Node oHead)
{
    if (oHead == null)
    {
        return null;
    }
    // 1."伸长"
    for (Node oMove = oHead; oMove != null; oMove = oMove.next)
    {
        // 复制结点
        Node copy = new Node(oMove.val);
    // 插入复制结点到原结点的后面
        copy.next = oMove.next;
        oMove.next = copy;
        // 移动到复制结点处
        oMove = copy;
    }
    // 2.连接好slibing
    for (Node oMove = oHead; oMove != null; oMove = oMove.next)
    {
        if (oMove.slibing == null)
        {
            continue;
        }
        Node copy = oMove.next;
        copy.slibing = oMove.slibing.next;
        oMove = copy;
    }
    // 3."分裂"，连接好原链表的next和复制链表中的next
    Node cHead = oHead.next;
    oHead.next = cHead.next;
    cHead.next = null;
    for (Node oMove = oHead.next, cMove = cHead; oMove != null; oMove = oMove.next, cMove = cMove.next)
    {
        Node copy = oMove.next;
        oMove.next = copy.next;
        copy.next = null;
        cMove.next = copy;
    }
    return cHead;
}