ccyy's coding zone
往前走,不要留恋路边的风景.
posts - 25,comments - 9,trackbacks - 0
   

题目:有一个链表L,其每个节点有2个指针,一个指针next指向链表的下个节点,另一个random随机指向链表中的任一个节点,可能是自己或者为空,写一个程序,要求复制这个链表的结构并分析其复杂性

 

解决方法一:

O(n)的复杂度,扫面两边即可。

                                                                 图【1】
图【1】是需要复制的链表


                                                              图【2】

如图【2】所示,ABCD是原来的链表,A’B’C’D’是复制的链表,第一遍扫描顺序复制next指针,把ABCDnext分别指向A’B’C’D’,将A’next指针指向BB’next指针指向C,依次类推

复制random指针: A’->random=A->random->next

恢复:A->next=A’->next;A’->next=A’->next->next;

 

 

解决方法二:

也是O(n)的时间复杂度。。。


                                                                    图【3】

 

如图【3】,第一次遍历将要复制的链表A’ B’ C’ D’插入员链表中,然后再一次遍历复制random指针:A->next->random=A->random->next;

恢复很简单:A->next=A->next->next;A’-next=A’->next->next;


转载请注明出处。

posted on 2011-04-02 23:01 ccyy 阅读(4704) 评论(2)  编辑 收藏 引用 所属分类: C/C++

FeedBack:
# re: 一个链表问题:复制带随机指针的链表
2011-04-29 17:30 | junfeng_feng
连个方法,明明一样啊...  回复  更多评论
  
# re: 一个链表问题:复制带随机指针的链表
2011-04-29 17:30 | junfeng_feng
@junfeng_feng
两个方法..一样  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理