欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指offer25:复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),结果返回复制后复杂链表的head。

程序员文章站 2022-06-30 08:38:11
1 题目描述 输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空) 2 思路和方法 考察链表的遍历知识,和对链表中添加节点细节的考察。 同 ......

1 题目描述

  输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

2 思路和方法

  考察链表的遍历知识,和对链表中添加节点细节的考察。 同时也考察了对于复杂问题的划分为多个子问题的能力,复杂问题划分为子问题来做。 

剑指offer25:复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),结果返回复制后复杂链表的head。


  其中实现代表next域,即1->2->3->4为最常见的链表形式。而虚线则代表了特殊指针,可以指向任意节点(包括自身和null)。比如1的特殊指针指向3,2的特殊指针指向1,3的特殊指针指向null,4的特殊指针也指向3。

  思路:利用next域复制原链表的时候,把每一个节点的副本都连接在该节点的后面,这样我们也可以在o(1)的时间内查找到random域位置。

  方法:比如我们把上图按这样的方式复制链表为:

剑指offer25:复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),结果返回复制后复杂链表的head。

然后我们为复制的每一节点初始化其random域,比如4的random域为3,那么4’的random域为3’,这样可以通过3.next直接得到了3’的位置,同理对其他节点也是这样处理,得到:

剑指offer25:复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),结果返回复制后复杂链表的head。

  最后一步就是拆分这个链表得到原链表和复制链表,原链表的节点都处于奇数位置,复制链表的节点都处于偶数位置。拆分如下:

  剑指offer25:复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),结果返回复制后复杂链表的head。

  步骤

第一步,依然根据原始链表的的每个节点n创建对应的n’,这一次,我们把n‘连接在n的后面;

第二步,设置复制出来的节点的random。假设原来链表上的n的random指向s,那么其对应的复制出来的n‘指向n的random的下一个节点s‘;

第三步,把这个长链表拆分为两个链表:把奇数位置的节点用next连接起来就是原始链表,把偶数位置的节点用next连接起来就是复制的链表。    

3 c++核心代码

 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 };

4 c++完整代码

  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