七十、反轉(zhuǎn)和合并鏈表、 鏈表有環(huán)的判斷

「@Author：Runsen」

?

編程的本質(zhì)來(lái)源于算法，而算法的本質(zhì)來(lái)源于數(shù)學(xué)，編程只不過(guò)將數(shù)學(xué)題進(jìn)行代碼化。「---- Runsen」

?

最近在重新梳理學(xué)算法的知識(shí)，本文為鏈表常見(jiàn)操作復(fù)習(xí)的總結(jié)文章，會(huì)講解常見(jiàn)的鏈表題目實(shí)現(xiàn)思路及附上答案，這些題目在leetcode上對(duì)應(yīng)的題號(hào)也有給出，好好學(xué)習(xí)算法吧～

• 單鏈表反轉(zhuǎn)
• 鏈表中環(huán)的檢測(cè)
• 兩個(gè)有序的鏈表合并
• K個(gè)有序的鏈表合并

leetcode 對(duì)應(yīng)題號(hào)：206，141，21，23

LeetCode 第 206 題：反轉(zhuǎn)鏈表

反轉(zhuǎn)一個(gè)單鏈表。

示例:?
輸入:?1->2->3->4->5->NULL
輸出:?5->4->3->2->1->NULL?

題目不難，定義三個(gè)變量pre、cur、cur.next，分別記錄上一個(gè)結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)、下一個(gè)結(jié)點(diǎn)。

反轉(zhuǎn)一個(gè)單鏈表需要當(dāng)前節(jié)點(diǎn)的next指針指向上一個(gè)結(jié)點(diǎn)pre，當(dāng)前節(jié)點(diǎn)的指針指向下一個(gè)結(jié)點(diǎn)，上一個(gè)結(jié)點(diǎn)的指針指向當(dāng)前節(jié)點(diǎn)。

通過(guò)迭代，依次反轉(zhuǎn)結(jié)點(diǎn)指向。具體代碼如下

class?Solution:
????def?reverseList(self,?head):
????????cur,?prev?=?head,?None
????????while?cur:
????????????cur.next,?prev,?cur?=?prev,?cur,?cur.next
????????return?prev

LeetCode 第 141 題：判斷鏈表中是否有環(huán)

遍歷整個(gè)數(shù)組, 給出的數(shù)據(jù)包含在集合中則說(shuō)明有環(huán), 返回 True; 若遍歷完畢, 則說(shuō)明無(wú)環(huán), 返回 False，如果用列表也是一樣。

「暴力解法」

class?Solution:
????def?hasCycle(self,?head:?ListNode)?->?bool:
????????"""
????????暴力法：通過(guò)遍歷鏈表，用set來(lái)存儲(chǔ)訪(fǎng)問(wèn)的節(jié)點(diǎn)，如果在set出現(xiàn)一樣的節(jié)點(diǎn)，說(shuō)明有壞，時(shí)間復(fù)雜度O(n)
????????:type?head:?ListNode
????????:rtype:?bool
????????"""
????????st?=?set()
????????while?head:
????????????if?head?in?st:
????????????????return?True
????????????st.add(head)
????????????head?=?head.next
????????return?False


??????#?下面是列表
????????l?=?[]
????????while?head:
????????????if?head?in?l:
????????????????return?True
????????????else:
????????????????l.append(head)
????????????????head?=?head.next
????????return?False???

從頭遍歷到尾，發(fā)現(xiàn)指向null，說(shuō)明沒(méi)環(huán)。這明顯不靠譜。暴力的時(shí)間空間復(fù)雜度都是O(n)

題目要求用 空間復(fù)雜度。其實(shí)，這道題考的是「快慢指針」 空間復(fù)雜度

通過(guò)使用具有 不同速度 的快、慢兩個(gè)指針遍歷鏈表，空間復(fù)雜度可以被降低至。慢指針每次移動(dòng)一步，而快指針每次移動(dòng)兩步。

如果列表中不存在環(huán)，最終快指針將會(huì)最先到達(dá)尾部，此時(shí)我們可以返回 false。

可以想象這樣一個(gè)場(chǎng)景, 你和一個(gè)朋友一起散步, 你每次移動(dòng)兩步, 朋友每次一步, 如為單向定長(zhǎng)道路, 你必然先到達(dá)重點(diǎn). 若是環(huán)繞操場(chǎng),則你們終將相遇.

class?Solution(object):
????def?hasCycle(self,?head):
????????slow?=?fast?=?head
????????while?slow?and?fast?and?fast.next:
????????????slow?=?slow.next
????????????fast?=?fast.next.next
????????????if?slow?==?fast:
????????????????return?True
????????return?False

LeetCode ?第21題：合并兩個(gè)有序鏈表

將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

示例：?

輸入：1->2->4,?1->3->4
輸出：1->1->2->3->4->4

從兩鏈表第一個(gè)結(jié)點(diǎn)開(kāi)始比較結(jié)點(diǎn)的值，取較小者作為合并鏈表的元素，依次進(jìn)行；后面如果有一個(gè)鏈表為空，則直接把不為空的鏈表接到合并鏈表的后面。

這個(gè)解決的方法使用遞歸，如果L1為空就返回L2，L2為空返回L1，L1的val<=L2的val，那么繼續(xù)遞歸。

#?Definition?for?singly-linked?list.
#?class?ListNode:
#?????def?__init__(self,?x):
#?????????self.val?=?x
#?????????self.next?=?None


class?Solution(object):
?def?mergeTwoLists(self,?l1,?l2):
??"""
??:type?l1:?ListNode
??:type?l2:?ListNode
??:rtype:?ListNode
??"""
??#遞歸的結(jié)束點(diǎn)就是L1或者L2為空就返回
??#如果L1為空就返回L2，L2為空返回L1
??#?if?not?(l1?and?l2):
???#?return?l1?if?l1?else?l2
??if?not?l1:
????????????return?l2
????????elif?not?l2:
????????????return?l1
??#L1的val<=L2的val，那么繼續(xù)遞歸
??#當(dāng)前L1的next指向一個(gè)遞歸函數(shù)
??#意思是L1的下一個(gè)和L2哪個(gè)大，就作為當(dāng)前L1的next
???elif?l1.val<=l2.val:
???l1.next?=?self.mergeTwoLists(l1.next,l2)
???return?l1
??else:
???l2.next?=?self.mergeTwoLists(l1,l2.next)
???return?l2

遞歸的代碼看起來(lái)是十分簡(jiǎn)潔的

LeetCode 第 23 題：合并 k 個(gè)排序鏈表

合并 k 個(gè)排序鏈表，返回合并后的排序鏈表。請(qǐng)分析和描述算法的復(fù)雜度。

示例:?
輸入:
[
?1->4->5,
?1->3->4,
?2->6
]
輸出:?1->1->2->3->4->4->5->6?

第一種法就是常規(guī)暴力思路，直接將所有的元素取出，然后排個(gè)序，再重組就達(dá)到了目的。

遍歷所有鏈表，將所有節(jié)點(diǎn)的值放到一個(gè)數(shù)組中。將這個(gè)數(shù)組排序，然后遍歷所有元素得到正確順序的值。用遍歷得到的值，創(chuàng)建一個(gè)新的有序鏈表。

時(shí)間復(fù)雜度： ，其中 N 是節(jié)點(diǎn)的總數(shù)目

空間復(fù)雜度：。

排序花費(fèi)空間（這取決于你選擇的算法）。創(chuàng)建一個(gè)新的鏈表花費(fèi) 的空間。

#?Definition?for?singly-linked?list.
#?class?ListNode:
#?????def?__init__(self,?x):
#?????????self.val?=?x
#?????????self.next?=?None


class?Solution:
????def?mergeKLists(self,?lists:?List[ListNode])?->?ListNode?:
????????"""
????????:type?lists:?List[ListNode]
????????:rtype:?ListNode
????????"""
????????self.nodes?=?[]
????????head?=?point?=?ListNode(0)
????????for?l?in?lists:
????????????while?l:
????????????????self.nodes.append(l.val)
????????????????l?=?l.next
????????for?x?in?sorted(self.nodes):
????????????point.next?=?ListNode(x)
????????????point?=?point.next
????????return?head.next

「人生最重要的不是所站的位置，而是內(nèi)心所朝的方向。只要我在每篇博文中寫(xiě)得自己體會(huì)，修煉身心；在每天的不斷重復(fù)學(xué)習(xí)中，耐住寂寞，練就真功，不畏艱難，奮勇前行，不忘初心，砥礪前行，人生定會(huì)有所收獲，不留遺憾 （作者：Runsen ）」

?

本文已收錄 GitHub，傳送門(mén)~^[1] ，里面更有大廠(chǎng)面試完整考點(diǎn)，歡迎 Star。

?

Reference