剑指offer之复杂链表的复制

剑指offer之复杂链表的复制

欢迎关注作者简书
csdn传送门

题目

  请实现函数ComplexListNode* Clone(ComplexListNode* pHead)，复制一个复杂链表。

  在复杂链表中，每个结点除了有一个pNext指针指向下一个结点之外，还有一个pSibling指向链表中的任意结点或者NULL。

  结点的定义如下：

public static class ComplexListNode {
        int value;
        ComplexListNode next;
        ComplexListNode sibling;
}

思路

方法1：（推荐）

  方法1是通过链表查找来得到pSibling指针所指向的结点，实际上我们可以通过空间换取时间，将原始链表和复制链表的结点通过哈希表对应起来，这样查找的时间就从O(N)变为O(1)。具体如下：

  复制原始链表上的每个结点N创建N'，然后把这些创建出来的结点用pNext连接起来。同时把<N,N'>的配对信息方法一个哈希表中；然后设置复制链表中的每个结点的pSibling指针，如果原始链表中结点N的pSibling指向结点S，那么在复制链表中，对应的N'应该指向S'。

  时间复杂度：O(N)

方法2：

  在不使用辅助空间的情况下实现O(N)的时间效率。

  第一步：根据原始链表的每个结点N创建对应的N'，然后将N‘通过pNext接到N的后面；

  第二步：设置复制出来的结点的pSibling。假设原始链表上的N的pSibling指向结点S，那么其对应复制出来的N'是N->pNext指向的结点，同样S'也是结点S->pNext指向的结点。

  第三步：把长链表拆分成两个链表，把奇数位置的结点用pNext连接起来的就是原始链表，把偶数位置的结点通过pNext连接起来的就是复制链表。

源码

方法1：（推荐）

/**
 * @program:
 * @description:
 * @author: zhouzhixiang
 * @create: 2018-11-17 20:21
 */
public class Test25_2 {
    public static class ComplexListNode {
        int value;
        ComplexListNode next;
        ComplexListNode sibling;
    }

    /**
     * 复杂链表的复制，使用复制链接法（推荐）
     * @param head
     * @return
     */
    public static ComplexListNode clone(ComplexListNode head) {
        if (head == null) return null;
        Map<ComplexListNode, ComplexListNode> map = new HashMap<>();
        ComplexListNode newHead = head;
        ComplexListNode Head = head;
        ComplexListNode newMove = newHead;
        map.put(head, newHead);
        while (head != null) {
            head = head.next;
            newMove.next = head;
            newMove = newMove.next;
            map.put(head, newMove);
        }

        newMove = newHead;
        head = Head;
        while (head != null) {
            if(head.sibling != null){
                newMove.sibling = map.get(head.sibling);
                head = head.next;
                newMove = newMove.next;
            }
        }
        return newHead;
    }

}

方法2：

package com.scmd;

/**
 * @program:
 * @description:
 * @author: zhouzhixiang
 * @create: 2018-11-17 19:26
 */
public class Test25 {

    public static class ComplexListNode {
        int value;
        ComplexListNode next;
        ComplexListNode sibling;
    }

    /**
     * 复制复杂链表
     * @param head
     * @return
     */
    public static ComplexListNode clone(ComplexListNode head) {
        if(head == null) return null;
        // 先复制结点
        cloneNodes(head);
        // 再链接sibling
        connectNodes(head);
        // 将整个链表拆分，返回复制链表的头结点
        return reconnectNodes(head);
    }

    /**
     * 复制一个链表，并且将复制后的结点插入到被复制结点的后面，只链接复制结点的next字段
     * @param head 待复制链表的头结点
     */
    private static void cloneNodes(ComplexListNode head) {
        while (head != null) {
            ComplexListNode temp = new ComplexListNode();
            temp.value = head.value;
            temp.next = head.next;
            head.next = temp;
            head = temp.next;
        }
    }

    /**
     * 设置复制结点的sibling字段
     * @param head
     */
    private static void connectNodes(ComplexListNode head) {
        while (head != null) {
            if(head.sibling != null) {
                head.next.sibling = head.sibling.next;
            }
            head = head.next.next;
        }
    }

    /**
     * 将复制结点和被复制结点分开，还原被复制的链表，同时生成监制链表
     * @param head  链表的头结点
     * @return  返回复制链表的头结点
     */
    private static ComplexListNode reconnectNodes(ComplexListNode head) {
        if(head == null) return null;
        ComplexListNode newHead = head.next;
        ComplexListNode move = newHead;
        head.next = newHead.next;
        head = head.next;
        while (head != null) {
            move.next = head.next;
            move = move.next;
            head.next = move.next;
            head = head.next;
        }
        return newHead;
    }

    /**
     * 输出链表信息
     * @param head
     */
    public static void printList(ComplexListNode head) {
        while (head != null) {
            System.out.print(head.value + "->");
            head = head.next;
        }
        System.out.println("null");
    }

    /**
     * 判断两个链表是否是同一个链表，不是值相同
     * @param head1
     * @param head2
     * @return
     */
    public static boolean isSame(ComplexListNode head1, ComplexListNode head2) {
        while (head1 != null && head2 != null) {
            if(head1 == head2) {
                head1 = head1.next;
                head2 = head2.next;
            }else {
                return false;
            }
        }
        return head1 == null && head2 == null;
    }
}

欢迎加入Java猿社区

欢迎加入Java猿社区.png