-
Notifications
You must be signed in to change notification settings - Fork 3
/
copy_random_list_doc.html
24 lines (23 loc) · 9.23 KB
/
copy_random_list_doc.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
<html>
<head>
<title>Evernote Export</title>
<basefont face="Tahoma" size="2" />
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="exporter-version" content="Evernote Windows/209040 (zh-CN); Windows/6.1.7601 Service Pack 1;"/>
<style>
body, td {
font-family: Tahoma;
font-size: 10pt;
}
</style>
</head>
<body>
<a name="8400"/>
<div>
<h1 style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0.5em; padding-left: 1.5em; font-size: 15px; font-family: 'Microsoft yahei', verdana, sans-serif; border-bottom-width: 2px; border-bottom-style: dotted; border-bottom-color: rgb(102, 102, 102); color: rgb(102, 102, 102);"><span style="font-family: verdana, sans-serif; font-size: 12px; line-height: 18px; text-align: left;"><img alt="转载" border="0" height="15" src="http://blog.csdn.net/images/turnship.gif" style="cursor:default;vertical-align:middle;" width="15"></img> 带随机指针的链表复制问题<span> </span><cite style="font-style: normal; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 5px; display: inline; text-decoration: none; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"><a style="text-decoration: none; color: rgb(102, 102, 102); font: normal normal normal 12px/normal Tahoma, sans-serif; padding-top: 1px; padding-right: 25px; padding-bottom: 1px; padding-left: 10px; background-image: url(http://blog.csdn.net/images/share-add.gif); background-attachment: initial; background-origin: initial; background-clip: initial; background-color: initial; background-position: 0px 0px; background-repeat: no-repeat no-repeat;" title="收藏到我的网摘中，并分享给我的朋友">收藏</a></cite></span></h1><div style="float: left; width: 517px; font-size: 14px; line-height: 21px;"><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 1em; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px;"></p><div><a href="http://www.cppblog.com/yuech/archive/2011/04/02/143318.html" style="text-decoration: none; color: rgb(102, 102, 102);">一个链表问题：复制带随机指针的链表</a></div>
<p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 1em; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px;"><span style="line-height: 21px;"><span style="line-height: 21px;">题目</span></span><span style="line-height: 21px;"><span style="line-height: 21px;">:</span></span><span style="line-height: 21px;"><span style="line-height: 21px;">有一个链表</span></span><span style="line-height: 21px;"><span style="line-height: 21px;">L,</span></span><span style="line-height: 21px;"><span style="line-height: 21px;">其每个节点有</span></span><span style="line-height: 21px;"><span style="line-height: 21px;">2</span></span><span style="line-height: 21px;"><span style="line-height: 21px;">个指针，一个指针</span></span><span style="line-height: 21px;"><span style="line-height: 21px;">next</span></span><span style="line-height: 21px;"><span style="line-height: 21px;">指向链表的下个节点，另一个</span></span><span style="line-height: 21px;"><span style="line-height: 21px;">random</span></span><span style="line-height: 21px;"><span style="line-height: 21px;">随机指向链表中的任一个节点，可能是自己或者为空，写一个程序，要求复制这个链表的结构并分析其复杂性</span></span></p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 1em; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px;"><span style="line-height: 21px;"> </span></p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 1em; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px;"><span style="line-height: 21px;"><span style="line-height: 21px;">解决方法一：</span></span></p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 1em; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px;"><span style="line-height: 21px;"><span style="line-height: 21px;">O(n)</span></span><span style="line-height: 21px;"><span style="line-height: 21px;">的复杂度</span></span><span style="line-height: 21px;"><span style="line-height: 21px;">,</span></span><span style="line-height: 21px;"><span style="line-height: 21px;">扫面两边即可。<br><img src="copy_random_list_doc_files/Image.jpg" type="image/jpeg" border="0" style="cursor:default;vertical-align:middle;"/><br>
图【1】<br>
图【1】是需要复制的链表<br></span></span></p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 1em; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px;"><img src="copy_random_list_doc_files/Image [1].jpg" type="image/jpeg" border="0" style="cursor:default;vertical-align:middle;"/><br>
图【2】</p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 1em; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px;"><span style="line-height: 21px;">如图【2】所示，</span><span style="line-height: 21px;">ABCD</span><span style="line-height: 21px;">是原来的链表，</span><span style="line-height: 21px;">A’B’C’D’</span><span style="line-height: 21px;">是复制的链表，第一遍扫描顺序复制</span><span style="line-height: 21px;">next</span><span style="line-height: 21px;">指针，把</span><span style="line-height: 21px;">ABCD</span><span style="line-height: 21px;">的</span><span style="line-height: 21px;">next</span><span style="line-height: 21px;">分别指向</span><span style="line-height: 21px;">A’B’C’D’</span><span style="line-height: 21px;">，将</span><span style="line-height: 21px;">A’</span><span style="line-height: 21px;">的</span><span style="line-height: 21px;">next</span><span style="line-height: 21px;">指针指向</span><span style="line-height: 21px;">B</span><span style="line-height: 21px;">，</span><span style="line-height: 21px;">B’</span><span style="line-height: 21px;">的</span><span style="line-height: 21px;">next</span><span style="line-height: 21px;">指针指向</span><span style="line-height: 21px;">C</span><span style="line-height: 21px;">，依次类推</span></p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 1em; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px;"><span style="line-height: 21px;">复制</span><span style="line-height: 21px;">random</span><span style="line-height: 21px;">指针：</span><span style="line-height: 21px;"><span> </span>A’->random=A->random->next</span></p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 1em; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px;"><span style="line-height: 21px;">恢复</span><span style="line-height: 21px;">:A->next=A’->next;A’->next=A’->next->next;</span></p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 1em; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px;"><span style="line-height: 21px;">解决方法二：</span></p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 1em; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px;"><span style="line-height: 21px;">也是</span><span style="line-height: 21px;">O(n)</span><span style="line-height: 21px;">的时间复杂度。。。</span></p><p align="left" style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 1em; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px;"><img src="copy_random_list_doc_files/Image [2].jpg" type="image/jpeg" border="0" style="cursor:default;vertical-align:middle;"/><br>
图【3】</p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 1em; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px;"><span style="line-height: 21px;">如图【3】，第一次遍历将要复制的链表</span><span style="line-height: 21px;">A’ B’ C’ D’</span><span style="line-height: 21px;">插入员链表中，然后再一次遍历复制</span><span style="line-height: 21px;">random</span><span style="line-height: 21px;">指针：</span><span style="line-height: 21px;">A->next->random=A->random->next;</span></p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 1em; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px;"><span style="line-height: 21px;">恢复很简单：</span><span style="line-height: 21px;">A->next=A->next->next;A’-next=A’->next->next;</span></p></div></div></body></html>