剑指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
