输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点,虚线部分），返回结果为复制后复杂链表的head。
解题思路：
1、遍历链表，复制链表中的每个结点，并将复制的结点插入到该结点的后面。例如，原链表为A->B->C, 遍历完毕后，链表变为A->A'->B->B'->C->C'，其中A‘，B'，C'是结点A，B，C的复制结点。
看图中，蓝色箭头为next指针：
复制结点后：
2、为复制结点的random指针赋值
如果原结点的random指针指向的是结点B，那么将复制结点的random指针指向结点B的复制结点B'。
图中黑色箭头为random指针：
复制结点的random指针赋值后：
3、将链表的原始结点与复制结点分割至两个链表，使原始结点构成一个链表，复制结点构成一个链表。
代码实现：
- (void)viewDidLoad { [super viewDidLoad]; [self copyNode]; } - (void)copyNode { Node * root = [Node nodeWithArray:@[@(1),@(2),@(3),@(4),@(5),]]; NSMutableArray<Node *> * array = [NSMutableArray array]; Node * temp = root; while (temp) { [array addObject:temp]; temp = temp.next; } root.sibling = array[2]; array[1].sibling = array.lastObject; array[3].sibling = array[1]; // 复制这个root链表, 生成一个全新的,但是一样的链表,类似于数组的深拷贝 // 1.在原始节点后面生成一个一模一样的节点, A->a->B->b->....->F->f // 2.把a.sibling = A.sibling.next; // 3.把下标为奇数的拆出成一个新链表 NSLog(@"原始链表root %@",root); temp = root; // 1.处理原始链表,生成一个这样的结构,A->a->B->b->....->F->f while (temp) { Node * newNode = [[Node alloc] init]; newNode.data = temp.data; newNode.next = temp.next; temp.next = newNode; temp = newNode.next; } NSLog(@"第一步root %@",root); // 2.next指针处理好了, 处理sibling指针了 temp = root; // 处理对应的a.sibling = A.sibling.next while (temp) { Node * copyNode = temp.next; copyNode.sibling = temp.sibling.next; temp = copyNode.next; } NSLog(@"第二步root %@",root); // 3.把下标为奇数的拆出成新链表,原始链表复原 Node * result = root.next; Node * resultTemp = nil; temp = root; while (temp) { Node * copyNode = temp.next; resultTemp.next = copyNode; resultTemp = copyNode; // 原始链表复原,A->B->C->D->... temp.next = copyNode.next; temp = copyNode.next; } NSLog(@"第三步root %@",root); NSLog(@"第三步result %@",result); } #import <Foundation/Foundation.h> @interface Node : NSObject // 根据数组生成一个链表 + (Node *)nodeWithArray:(NSArray *)array; @property (nonatomic, assign) int data; @property (nonatomic, strong) Node *next; @property (nonatomic, strong) Node *sibling;/// 随机的一个节点 @end ------ #import "Node.h" @implementation Node + (Node *)nodeWithArray:(NSArray *)array { if (array.count==0) { return nil; } Node * first = [[Node alloc] init]; first.data = [array.firstObject intValue]; Node * preNode = first; for (int i = 1; i<array.count; i++) { Node * next = [[Node alloc] init]; next.data = [array[i] intValue]; preNode.next = next; preNode = next; } return first; } - (NSString *)description { return [NSString stringWithFormat:@"原始值:%d 下标值:%d %@",self.data,self.sibling.data,self.next]; } @end上面的这种算法对思路的要求太高了, 除非以前专门想过, 否则在面试过程中想出这样的算法几乎不可能, 下面是更通用的一种思路.
对于A->B->C->.... 生成一个对应的a->b->c->... , a.data = A.data, a.sibling=A.sibling , 在生成a链表的同时, 用一个mapTable保存A(key)->a(value)的映射关系, 此时a.sibling是指向A链表中的某个元素, 需要修改a.sibling指向成a链表中的元素, 借助mapTable的映射关系(A->a,B->b,C->c,D-d), 在遍历a组成的链表, 修改a.sibling = [mapTable objectForKey:a.sibling] , 即可完成a.sibling指向.
这种思路需要借助一个O(n)的额外空间, 比上一种方式占用内存更大一点. 但是思路比较清晰好理解, 操作也没有那么复杂
- (void)viewDidLoad { [super viewDidLoad]; [self copyNodeUseDic]; } - (void)copyNodeUseDic { Node * root = [Node nodeWithArray:@[@(1),@(2),@(3),@(4),@(5),]]; NSMutableArray<Node *> * array = [NSMutableArray array]; Node * temp = root; while (temp) { [array addObject:temp]; temp = temp.next; } root.sibling = array[2]; array[1].sibling = array.lastObject; array[3].sibling = array[1]; // 复制这个root链表, 生成一个全新的,但是一样的链表,类似于数组的深拷贝 // 1.生成结果链表,用一个map建立A-a之间的映射关系,把a.sibling指向A.sibling // 2.根据映射关系修改a.sibling NSLog(@"原始链表root \n%@",root); Node * result = nil; Node * resultPre = nil; NSMapTable * mapTable = [NSMapTable strongToStrongObjectsMapTable]; temp = root; while (temp) { Node * newNode = [[Node alloc] init]; newNode.data = temp.data; newNode.sibling = temp.sibling; // 建立 A->a之间的映射关系 [mapTable setObject:newNode forKey:temp]; resultPre.next = newNode; resultPre = newNode; if (result == nil) { result = newNode; } temp = temp.next; } NSLog(@"第一步result \n%@",result); // 根据映射关系,修改a.sibling值 temp = result; while (temp) { // 比如A.sibling = B , 现在a.sibling也是指向B的,B在map对应b, 所以a.sibling = [mapTable objectForKey:a.sibling] if (temp.sibling) { temp.sibling = [mapTable objectForKey:temp.sibling]; } temp = temp.next; } NSLog(@"第二步result \n%@",result); }
