我要评论
立花律子,拉登团购,兵行人间
考察链表的遍历知识，和对链表中添加节点细节的考察。 同时也考察了对于复杂问题的划分为多个子问题的能力，复杂问题划分为子问题来做。
其中实现代表next域，即1->2->3->4为最常见的链表形式。而虚线则代表了特殊指针，可以指向任意节点（包括自身和null)。比如1的特殊指针指向3,2的特殊指针指向1，3的特殊指针指向null，4的特殊指针也指向3。
思路：利用next域复制原链表的时候，把每一个节点的副本都连接在该节点的后面，这样我们也可以在o(1)的时间内查找到random域位置。
方法：比如我们把上图按这样的方式复制链表为：
然后我们为复制的每一节点初始化其random域，比如4的random域为3，那么4’的random域为3’，这样可以通过3.next直接得到了3’的位置，同理对其他节点也是这样处理，得到：
最后一步就是拆分这个链表得到原链表和复制链表，原链表的节点都处于奇数位置，复制链表的节点都处于偶数位置。拆分如下：
步骤：
第一步，依然根据原始链表的的每个节点n创建对应的n’，这一次，我们把n‘连接在n的后面；
第二步，设置复制出来的节点的random。假设原来链表上的n的random指向s，那么其对应的复制出来的n‘指向n的random的下一个节点s‘；
第三步，把这个长链表拆分为两个链表：把奇数位置的节点用next连接起来就是原始链表，把偶数位置的节点用next连接起来就是复制的链表。
1 /*
2 struct randomlistnode {
3 int label;
4 struct randomlistnode *next, *random;
5 randomlistnode(int x) :
6 label(x), next(null), random(null) {
7 }
8 };
9 */
10 class solution {
11 public:
12 randomlistnode* clone(randomlistnode* phead)
13 {
14 if(phead==null)
15 return null;
16 randomlistnode* cur; //两个链表节点指针
17 cur = phead;
18 while(cur){
19 randomlistnode* node = new randomlistnode(cur->label); //复制头指针
20 node->next = cur->next;
21 cur->next = node;
22 cur = node->next;
23 } //新链表和旧链表链接：a->a'->b->b'->c->c'
24 cur = phead;
25 randomlistnode* p;
26 while(cur){
27 p = cur->next;
28 if(cur->random)
29 p->random = cur->random->next; //关键
30 cur = p->next;
31 }
32 randomlistnode* temp;
33 randomlistnode* phead = phead->next;
34 cur = phead;
35 while(cur->next){
36 temp = cur->next;
37 cur->next = temp->next;
38 cur = temp;
39 }
40 return phead;
41 }
42 };
1 // 剑指offer 面试题26 复杂链表的复制
2 #include <iostream>
3 using namespace std;
4
5 struct complexlistnode
6 {
7 int m_nvalue;
8 complexlistnode* m_pnext;
9 complexlistnode* m_psibling;
10
11 complexlistnode(){ m_nvalue = 0; m_pnext = null; m_psibling = null; }
12 complexlistnode(int value){ m_nvalue = value; m_pnext = null; m_psibling = null; }
13
14 };
15
16 /*不借助辅助空间的情况下实现o(n)的时间效率*/
17
18 // 第一步，根据原始链表的每个节点n，复制出n'，把n'链接在对应的n后面
19 void clonenodes(complexlistnode* phead)
20 {
21 complexlistnode* pnode = phead;
22 while (pnode)
23 {
24 complexlistnode* pcloned = new complexlistnode();
25 pcloned->m_nvalue = pnode->m_nvalue;
26 // 先保存原来的n节点的next指针
27 pcloned->m_pnext = pnode->m_pnext;
28 // 不复制sibling指针
29 pcloned->m_psibling = null;
30 pnode->m_pnext = pcloned;
31 pnode = pcloned->m_pnext;
32 }
33 }
34
35 // 第二步，设置复制出来的节点的sibling指针
36 // 若原始链表上的n的sibling指针指向s，则复制出来的n指向s的next指向的节点s'
37 void connectsiblingnodes(complexlistnode* phead)
38 {
39 complexlistnode* pnode = phead;
40 while (pnode)
41 {
42 complexlistnode* pcloned = pnode->m_pnext;
43 if (pnode->m_psibling)
44 {
45 pcloned->m_psibling = pnode->m_psibling->m_pnext;
46 }
47 pnode = pcloned->m_pnext;
48 }
49 }
50
51 // 第3步，拆分链表，奇数位置的节点用next连接起来就是原始链表
52 // 偶数位置的节点用next链接起来就是复制出来的链表。
53
54 complexlistnode* reconnectnodes(complexlistnode* phead)
55 {
56 // 用于返回
57 complexlistnode* pclonedhead = null;
58
59 complexlistnode* pnode = phead;
60 complexlistnode* pclonednode = null;
61
62 if (pnode)
63 {
64 // 找到复制的链表头，更新当前复制链表节点
65 pclonedhead = pclonednode = pnode->m_pnext;
66
67 // 重连原始链表，更新当前原始链表节点
68 pnode->m_pnext = pclonednode->m_pnext;
69 pnode = pnode->m_pnext;
70 }
71
72 while (pnode)
73 {
74 pclonednode->m_pnext = pnode->m_pnext;
75 pclonednode = pclonednode->m_pnext;
76 pnode->m_pnext = pclonednode->m_pnext;
77 pnode = pnode->m_pnext;
78 }
79 return pclonedhead;
80
81 }
82
83 complexlistnode* clone(complexlistnode* phead)
84 {
85 clonenodes(phead);
86 connectsiblingnodes(phead);
87 return reconnectnodes(phead);
88 }
89
90
91 int main()
92 {
93 complexlistnode* p1 = new complexlistnode(7);
94 complexlistnode* p2 = new complexlistnode(2);
95 complexlistnode* p3 = new complexlistnode(3);
96 complexlistnode* p4 = new complexlistnode(4);
97 complexlistnode* p5 = new complexlistnode(5);
98 p1->m_psibling = p3;
99 p2->m_psibling = p5;
100 p4->m_psibling = p2;
101 p1->m_pnext = p2;
102 p2->m_pnext = p3;
103 p3->m_pnext = p4;
104 p4->m_pnext = p5;
105
106 complexlistnode* pclonedlist = clone(p1);
107 cout << pclonedlist->m_nvalue << endl;
108
109
110 system("pause");
111 return 0;
112 }
https://blog.csdn.net/dawn_after_dark/article/details/80979501
https://blog.csdn.net/qq_33575542/article/details/80801610
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论