坚持每天两道剑指offer,今天看到复杂链表的复制.之前是没接触过这类的题.看到提出的三种解法,也是开了自己的脑洞.
第三种解法,只用O(n)的复杂度解决问题, 并且不需要额外的空间.
记录一下三种解法,最后在实现最后一种
复杂链表的结构
struct CompList{ int data; CompList* next; CompList* others; }; next指针是正常指向下一个节点, others是指向其他的节点,也可以是空.
L : a->b->c->d->e, a->others = c类似这样的.
下面的三种方法都以上面的量表为例
1.O(n^2)的复杂度
先把上面的链表复制得到 a'->b'->c'->d'->e',接下来因为a->others = c 所以a'->others =c'
这样,现在在L里找到c的位置需要走多少步,然后在L'内走相应的步数,在设置others指针,这样把整个链表遍历后既可以把L'的所有的others指针不为空的就可以设置好了.
分析一下复杂度
L' 里有n个节点, 每一个节点在设置others指针的时候都要从头遍历,走O(n)步,所以总的就是O(n^2)
这种算法,一般都能想的出来,但是复杂度高,如果面试,面试官应该会提醒考虑复杂度低的算法
2.以空间换时间O(n)空间,O(n)的时间
首先也是先遍历L, 同时复制出L', 在复制的过程中我们用map做一个映射, map[a] = a'这样
接下来去设置L'的others指针, a'->others = map[a->others], 这样就可以设置L'的others指针了
3.O(n)的时间完成
首先是复制,复制的形式不同,
(1)复制成a->a'->b->b'->c->c'->d->d'-e->e;
(2)我们设置L'的others指针,a'->others = a->others->next;
(3)把L'在链表里提出来变成
a->b->c->d->e, a'->b'->c'->d'->e';
实现第一步,复制链表
CompList* CloneNode(CompList* head){ CompList* newNode = head; while(newNode != NULL){ CompList* node = new CompList; node->data = newNode->data; node->others =NULL; node->next = newNode->next; newNode->next = node; newNode = node->next; } return head; } 实现第二步,设置L'的others指针
CompList* ConnectSiblingNodes(CompList* head){ CompList&* Pnode = head; while(Pnode != NULL){ CompList* node = Pnode->next; if(Pnode->others != NULL){ node->others = Pnode->others->next; } Pnode = node->next; } return head; }
最后提取链表
CompList* ReconnectNodes(CompList* head){ int flag = 0; CompList* node = head; CompList* CloneHead = NULL; CompList* CloneNode = NULL; if(node != NULL){ CloneHead = CloneNode = node->next; node->next = CloneNode->next; node = node->next; } while(node != NULL){ CloneNode->next = node->next; CloneNode = CloneNode->next; node->next = CloneNode->next; node = node->next; } return CloneHead; }
继续坚持每天保证两道offer题,加油
