-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLeetCode-147-Insertion-Sort-List.html
More file actions
287 lines (220 loc) · 15.3 KB
/
LeetCode-147-Insertion-Sort-List.html
File metadata and controls
287 lines (220 loc) · 15.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
<!DOCTYPE html>
<html>
<head>
<!-- [[! Document Settings ]] -->
<meta charset="utf-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<!-- [[! Page Meta ]] -->
<title>LeetCode 147 : Insertion Sort List</title>
<meta name="description" content="Make Today Better Than Yesterday - Code, Food, Photo and some Geek stuff ..." />
<meta name="HandheldFriendly" content="True" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<link rel="shortcut icon" href="/assets/images/favicon.ico" >
<!-- [[! Styles'n'Scripts ]] -->
<link rel="stylesheet" type="text/css" href="/assets/css/screen.css" />
<link rel="stylesheet" type="text/css"
href="//fonts.googleapis.com/css?family=Merriweather:300,700,700italic,300italic|Open+Sans:700,400" />
<link rel="stylesheet" type="text/css" href="/assets/css/syntax.css" />
<!-- [[! Ghost outputs important style and meta data with this tag ]] -->
<link rel="canonical" href="/" />
<meta name="referrer" content="origin" />
<link rel="next" href="/page2/" />
<meta property="og:site_name" content="Make Today Better Than Yesterday" />
<meta property="og:type" content="website" />
<meta property="og:title" content="Make Today Better Than Yesterday" />
<meta property="og:description" content="Code, Food, Photo and some Geek stuff ..." />
<meta property="og:url" content="/" />
<meta property="og:image" content="/assets/images/cover1.jpg" />
<meta name="twitter:card" content="summary_large_image" />
<meta name="twitter:title" content="Make Today Better Than Yesterday" />
<meta name="twitter:description" content="Code, Food, Photo and some Geek stuff ..." />
<meta name="twitter:url" content="/" />
<meta name="twitter:image:src" content="/assets/images/cover1.jpg" />
<script type="application/ld+json">
{
"@context": "http://schema.org",
"@type": "Website",
"publisher": "Finding The Way Home",
"url": "/",
"image": "/assets/images/cover1.jpg",
"description": "Code, Food, Photo and some Geek stuff ..."
}
</script>
<meta name="generator" content="Jekyll 3.0.0" />
<link rel="alternate" type="application/rss+xml" title="Make Today Better Than Yesterday" href="/rss.xml" />
</head>
<body class="home-template nav-closed">
<div class="nav">
<h3 class="nav-title">Menu</h3>
<a href="#" class="nav-close">
<span class="hidden">Close</span>
</a>
<ul>
<li class="nav-home " role="presentation"><a href="/">Home</a></li>
<li class="nav-about " role="presentation"><a href="/about">About</a></li>
<li class="nav-photo " role="presentation"><a href="/tag/photo">Photo</a></li>
<li class="nav-food " role="presentation"><a href="/tag/food">Food</a></li>
<li class="nav-geek " role="presentation"><a href="/tag/geek">Geek</a></li>
<li class="nav-code " role="presentation"><a href="/tag/code">Code</a></li>
<li class="nav-author " role="presentation"><a href="/author/CT">Author</a></li>
</ul>
<a class="subscribe-button icon-feed" href="/rss.xml">Subscribe</a>
</div>
<span class="nav-cover"></span>
<div class="site-wrapper">
<!-- [[! Everything else gets inserted here ]] -->
<!-- < default -->
<!-- The comment above "< default" means - insert everything in this file into -->
<!-- the [body] of the default.hbs template, which contains our header/footer. -->
<!-- Everything inside the #post tags pulls data from the post -->
<!-- #post -->
<header class="main-header post-head " style="background-image: url(/assets/images/cover_2.jpg) ">
<nav class="main-nav overlay clearfix">
<a class="blog-logo" href="/"><img src="/assets/images/ghost.png" alt="Blog Logo" /></a>
<a class="menu-button icon-menu" href="#"><span class="word">Menu</span></a>
</nav>
</header>
<main class="content" role="main">
<article class="post tag-code">
<header class="post-header">
<h1 class="post-title">LeetCode 147 : Insertion Sort List</h1>
<section class="post-meta">
<!-- <a href='/'>Ching Tsai</a> -->
<time class="post-date" datetime="2016-03-07">07 Mar 2016</time>
<!-- [[tags prefix=" on "]] -->
on
<a href='/tag/code'>Code</a>
</section>
</header>
<section class="post-content">
<blockquote>
<p>Sort a linked list using insertion sort.</p>
</blockquote>
<h3>Initial Though</h3>
<p>這題很有意思， insertion sort 可能是大家最熟悉的 n^2 sorting ， 原本認為用 array 來作 insert 要花很多時間在做資料搬移，但當做在單向的 LinkedList 卻用變得更棘手。</p>
<h3>Guide</h3>
<p>第一個遇到的問題就是要 maintain 前後兩個 node 的 next 要能指對。所以當有一個直鏈：<code>A->B->C</code> 若要用 <code>D</code> 取代 <code>B</code> 我就要確保 <code>A->D</code> 和 <code>D->C</code> 。 這個可以用一個暫存的 Object pre 來儲存。第二個問題就是 head 是沒有 parent ， 所以要用一個空的dummy_head 來當作假的 head。 最後就是這題用一個很不像傳統 insertion sort 的解法，也就是分成兩個鏈，一個是 dummy 開頭的 sorted 鏈 ， 一個就是原本 input 進來的鏈。所以每次從 input 鏈抓一個 node <code>cur</code> ， 然後到 sorted 鏈裡找到是適合的地方插進去，這樣的作法會比用同一條鏈還 maintain 兩個鏈來的容易很多。</p>
<h3>Code</h3>
<div class="highlight"><pre><code class="language-java" data-lang="java"><span class="cm">/**</span>
<span class="cm"> * Definition for singly-linked list.</span>
<span class="cm"> * public class ListNode {</span>
<span class="cm"> * int val;</span>
<span class="cm"> * ListNode next;</span>
<span class="cm"> * ListNode(int x) { val = x; }</span>
<span class="cm"> * }</span>
<span class="cm"> */</span>
<span class="kd">public</span> <span class="kd">class</span> <span class="nc">Solution</span> <span class="o">{</span>
<span class="n">ListNode</span> <span class="n">dummy_head</span> <span class="o">=</span> <span class="k">new</span> <span class="nf">ListNode</span><span class="o">(</span><span class="mi">0</span><span class="o">);</span>
<span class="kd">public</span> <span class="n">ListNode</span> <span class="nf">insertionSortList</span><span class="o">(</span><span class="n">ListNode</span> <span class="n">head</span><span class="o">)</span> <span class="o">{</span>
<span class="k">if</span><span class="o">(</span><span class="n">head</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span>
<span class="k">return</span> <span class="n">head</span><span class="o">;</span>
<span class="n">ListNode</span> <span class="n">pre</span><span class="o">,</span><span class="n">cur</span><span class="o">,</span><span class="n">iter</span><span class="o">;</span>
<span class="n">cur</span> <span class="o">=</span> <span class="n">head</span><span class="o">;</span>
<span class="k">while</span><span class="o">(</span><span class="n">cur</span> <span class="o">!=</span><span class="kc">null</span><span class="o">){</span>
<span class="n">iter</span> <span class="o">=</span> <span class="n">dummy_head</span><span class="o">;</span>
<span class="k">while</span><span class="o">(</span><span class="n">iter</span><span class="o">.</span><span class="na">next</span><span class="o">!=</span><span class="kc">null</span> <span class="o">&&</span> <span class="n">iter</span><span class="o">.</span><span class="na">next</span><span class="o">.</span><span class="na">val</span> <span class="o"><</span> <span class="n">cur</span><span class="o">.</span><span class="na">val</span><span class="o">){</span>
<span class="n">iter</span><span class="o">=</span> <span class="n">iter</span><span class="o">.</span><span class="na">next</span><span class="o">;</span>
<span class="o">}</span>
<span class="n">pre</span> <span class="o">=</span> <span class="n">cur</span><span class="o">.</span><span class="na">next</span><span class="o">;</span>
<span class="n">cur</span><span class="o">.</span><span class="na">next</span> <span class="o">=</span> <span class="n">iter</span><span class="o">.</span><span class="na">next</span><span class="o">;</span>
<span class="n">iter</span><span class="o">.</span><span class="na">next</span> <span class="o">=</span> <span class="n">cur</span><span class="o">;</span>
<span class="n">cur</span> <span class="o">=</span> <span class="n">pre</span><span class="o">;</span>
<span class="o">}</span>
<span class="k">return</span> <span class="n">dummy_head</span><span class="o">.</span><span class="na">next</span><span class="o">;</span>
<span class="o">}</span>
<span class="o">}</span>
</code></pre></div>
</section>
<footer class="post-footer">
<!-- Everything inside the #author tags pulls data from the author -->
<!-- #author-->
<figure class="author-image">
<a class="img" href="/author/CT" style="background-image: url(/assets/images/ct.png)"><span class="hidden">'s Picture</span></a>
</figure>
<section class="author">
<h4><a href="/author/CT">Ching Tsai</a></h4>
<p> 每天努力學習的研究攻城獅，略懂平行運算，分散式系統及機器學習，平時偶爾攝影，興趣是看 YouTube 學煮菜。</p>
<div class="author-meta">
<span class="author-location icon-location"> Hsinchu, Taiwan</span>
<span class="author-link icon-link"><a href="http://ChingTsai.github.io/chingtsai.github.io/"> ChingTsai.github.io/chingtsai.github.io/</a></span>
</div>
</section>
<!-- /author -->
<section class="share">
<h4>Share this post</h4>
<a class="icon-twitter" href="http://twitter.com/share?text=LeetCode 147 : Insertion Sort List&url=http://ChingTsai.github.io/chingtsai.github.io/LeetCode-147-Insertion-Sort-List"
onclick="window.open(this.href, 'twitter-share', 'width=550,height=235');return false;">
<span class="hidden">Twitter</span>
</a>
<a class="icon-facebook" href="https://www.facebook.com/sharer/sharer.php?u=http://ChingTsai.github.io/chingtsai.github.io/LeetCode-147-Insertion-Sort-List"
onclick="window.open(this.href, 'facebook-share','width=580,height=296');return false;">
<span class="hidden">Facebook</span>
</a>
<a class="icon-google-plus" href="https://plus.google.com/share?url=http://ChingTsai.github.io/chingtsai.github.io/LeetCode-147-Insertion-Sort-List"
onclick="window.open(this.href, 'google-plus-share', 'width=490,height=530');return false;">
<span class="hidden">Google+</span>
</a>
</section>
<!-- Add Disqus Comments -->
<div id="disqus_thread"></div>
<script type="text/javascript">
//var disqus_developer = 1;
/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */
var disqus_shortname = 'maketodaybetterthanyesterday'; // required: replace example with your forum shortname
var disqus_identifier = '/LeetCode-147-Insertion-Sort-List';
var disqus_url = 'http://ChingTsai.github.io/chingtsai.github.io//LeetCode-147-Insertion-Sort-List';
//console.log(disqus_shortname+" "+disqus_identifier+" "+disqus_url);
/* * * DON'T EDIT BELOW THIS LINE * * */
(function() {
var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
dsq.src = 'https://' + disqus_shortname + '.disqus.com/embed.js';
(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>
<noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
<a href="http://disqus.com" class="dsq-brlink">blog comments powered by <span class="logo-disqus">Disqus</span></a>
</div>
</footer>
</article>
</main>
<aside class="read-next">
<!-- [[! next_post ]] -->
<a class="read-next-story " style="background-image: url(/assets/images/cover_2.jpg)" href="/Shell-Script-Jekyll-Markdown-Generator">
<section class="post">
<h2>Shell Script : Jekyll Markdown Generator</h2>
<p>很多人都問我說為什麼要用 MAC？除了做工精良，續航力高，還有一點非常棒的就是他可以和 Linux 共用大部分的 Unix Script。以下就用一個小小的例子來解釋能寫一些簡單的 Script 可以讓工程師一天過的更愉快。 一開始的緣由在於 Jekyll 的 Markdown 有一個既定的格式，就是檔名要是 `日期-標題.md` 並且內部要以特定的...</p>
</section>
</a>
<!-- [[! /next_post ]] -->
<!-- [[! prev_post ]] -->
<a class="read-next-story prev " style="background-image: url(/assets/images/highlight.jpg)" href="/Jekyll-Markdown-Syntax-Highlighting">
<section class="post">
<h2>Jekyll Markdown Syntax Highlighting</h2>
<p>當初會被吸引來用 Jekyll 還來搭建這個 Blog ，其中一個很大的原因，也是因為內建的 Markdown expression 可以很方便的幫一些範例 Code 做美美的 Syntax Highlighting。不過 Highlighting 的 style...</p>
</section>
</a>
<!-- [[! /prev_post ]] -->
</aside>
<!-- /post -->
<footer class="site-footer clearfix">
<section class="copyright"><a href="/">Make Today Better Than Yesterday</a> © 2016</section>
<section class="poweredby">Proudly published with <a href="https://jekyllrb.com/">Jekyll</a> using <a href="https://github.com/biomadeira/jasper">Jasper</a></section>
</footer>
</div>
<!-- [[! Ghost outputs important scripts and data with this tag ]] -->
<script type="text/javascript" src="https://code.jquery.com/jquery-1.11.3.min.js"></script>
<!-- [[! The main JavaScript file for Casper ]] -->
<script type="text/javascript" src="/assets/js/jquery.fitvids.js"></script>
<script type="text/javascript" src="/assets/js/index.js"></script>
<!-- Add Google Analytics -->
<!-- Google Analytics Tracking code -->
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', '', 'auto');
ga('send', 'pageview');
</script>
</body>
</html>