七十一、去重交換排序鏈表、 求鏈表的中間結(jié)點

「@Author：Runsen」

?

編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學，編程只不過將數(shù)學題進行代碼化。「---- Runsen」

?

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

• 兩兩交換鏈表的節(jié)點
• 刪除排序鏈表中的重復元素
• 排序鏈表（重要）
• 鏈表的中間結(jié)點

leetcode 對應題號：24，83，148，876

LeetCode ?第24題：兩兩交換鏈表的節(jié)點

給定一個鏈表，兩兩交換其中相鄰的節(jié)點，并返回交換后的鏈表。

示例:?
給定?1->2->3->4,?你應該返回?2->1->4->3.

1——2——3——4：我們需要做的就是，將一指向三，將二指向一，如此我們就完成了反轉(zhuǎn)，后續(xù)只要一次遍歷即可。

思路：a,b,pre記錄三個指針，相鄰兩個，相鄰兩個元素前面的一個，第一步將節(jié)點 2 指向節(jié)點 1，然后再將節(jié)點 1 指向節(jié)點三。這一步交換完畢后鏈表變?yōu)?2->1->3->4。在進行下一次交換，將節(jié)點 4 指向節(jié)點 3，節(jié)點3指向none 但是還要注意節(jié)點 1 的指向，節(jié)點 1 要指向節(jié)點 4。

#?class?ListNode:
#?????def?__init__(self,?x):
#?????????self.val?=?x
#?????????self.next?=?None

class?Solution:
?def?swapPairs(self,head):
?????pre,?pre.next?=?self,?head
?????while?pre.next?and?pre.next.next:
?????????a?=?pre.next
?????????b?=?a.next
?????????pre.next,b.next?,a.next?=?b,a,b.next
?????????pre?=?a
?????????
?????return??self.next

eetCode ?第83題：刪除排序鏈表中的重復元素

給定一個排序鏈表，刪除所有重復的元素，使得每個元素只出現(xiàn)一次。

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

由于輸入的列表已排序，因此我們可以通過將結(jié)點的值與它之后的結(jié)點進行比較來確定它是否為重復結(jié)點。如果它是重復的，我們更改當前結(jié)點的 next 指針，以便它跳過下一個結(jié)點并直接指向下一個結(jié)點之后的結(jié)點。

如果遇到cur.val和cur.next.val重復,讓cur.next=cur.next.next

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

class?Solution:
????def?deleteDuplicates(self,?head:?ListNode)?->?ListNode:
????????h?=?head
????????while?head?and?head.next:
????????????if?head.val?==?head.next.val:
????????????????head.next?=?head.next.next
????????????else:
????????????????head?=?head.next
????????????????
????????return?h

class?Solution:
????def?deleteDuplicates(self,?head):
????????cur?=?root?=?head
????????while?head:
????????????if?head.val?!=?cur.val:
????????????????cur.next?=?cur?=?head
????????????head?=?cur.next?=?head.next
????????return?root

LeetCode 第 876題：鏈表的中間結(jié)點（重要）

#?輸入：[1,2,3,4,5]
#輸出：此列表中的結(jié)點 3 (序列化形式：[3,4,5])
#返回的結(jié)點值為 3 。?(測評系統(tǒng)對該結(jié)點序列化表述是?[3,4,5])。
#注意，我們返回了一個 ListNode 類型的對象 ans，這樣：
#ans.val?=?3,?ans.next.val?=?4,?ans.next.next.val?=?5,?以及?ans.next.next.next?=?NULL.
#?示例 2：?
#?輸入：[1,2,3,4,5,6]
#輸出：此列表中的結(jié)點 4 (序列化形式：[4,5,6])
#由于該列表有兩個中間結(jié)點，值分別為 3 和 4，我們返回第二個結(jié)點。
#?提示：?
#?給定鏈表的結(jié)點數(shù)介于 1 和 100?之間。?
#?Related?Topics?鏈表

「尋找鏈表的中間結(jié)點」

• 遍歷兩次。第一次遍歷求導鏈表長度，找出中間結(jié)點的長度值，第二層遍歷找到中間結(jié)點并返回；
• 快慢指針法。慢指針每次走一步，快指針每次走兩步，快指針走到鏈表末尾時，慢指針剛好走到鏈表中間。

「方法２時間復雜度更低，只需遍歷一次。」

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

class?Solution:
????def?middleNode(self,?head:?ListNode)?->?ListNode:
????????slow?=?head
????????fast?=?head
????????while??fast?and?fast.next:
????????????slow?=?slow.next
????????????fast?=?fast.next.next
????????return?slow

eetCode 第148題：排序鏈表（重要）

在 時間復雜度和常數(shù)級空間復雜度下，對鏈表進行排序。

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

題目要求時間空間復雜度分別為和，根據(jù)時間復雜度我們自然想到二分法，從而聯(lián)想到歸并排序。歸并排序，后面細聊。

利用歸并的思想，遞歸地將當前鏈表分為兩段，然后merge，分兩段的方法是使用 fast-slow 法，用兩個指針，一個每次走兩步，一個走一步，直到快的走到了末尾，然后慢的所在位置就是中間位置，這樣就分成了兩段。

歸并排序分為兩步，

1.找到待排序鏈表的中間節(jié)點（使用快慢指針法，leetcode 876題）

2.合并兩個有序鏈表（leetcode 21題），因此本題相當于結(jié)合這兩步來實現(xiàn)鏈表排序。

#?Definition?for?singly-linked?list.
class?ListNode:
????def?__init__(self,?x):
????????self.val?=?x
????????self.next?=?None
class?Solution:
????def?sortList(self,?head:?ListNode)?->?ListNode:
????????#?if?not?head?or?not?head.next:#
????????if?head?==?None?or?head.next?==?None:
????????????return?head?
????????slow??=?head?#快慢指針法找到鏈表中點
????????fast?=?head
????????while?fast.next?and?fast.next.next:
????????????slow?=?slow.next
????????????fast?=?fast.next.next
????????right?=?slow.next
????????#?print(right.val)
????????slow.next?=?None?#這一句的原因是?需要對中點前的鏈表進行割斷處理

????????l1?=?self.sortList(head)#遞歸保證l1和l2為有序鏈表
????????l2?=?self.sortList(right)
????????return?self.mergeTwoLists(l1,l2)
???#?合并兩個有序鏈表
????def?mergeTwoLists(self,?l1:?ListNode,?l2:?ListNode)?->?ListNode:
????????if?not?l1?and?not?l2:
????????????return?None
????????if?not?l1:
????????????return?l2
????????if?not?l2:
????????????return?l1
????????head?=?head1?=?ListNode(0)
????????while?l1?and?l2:
????????????if?l1.val?<=?l2.val:
????????????????head.next?=?l1
????????????????l1?=?l1.next
????????????else:
????????????????head.next?=?l2
????????????????l2?=?l2.next
????????????head?=?head.next
????????if?not?l1?:?head.next?=?l2
????????if?not?l2?:?head.next?=?l1
????????return?head1.next

下面是測試代碼

if?__name__?==?"__main__":
????n1?=?ListNode(4)
????n2?=?ListNode(7)
????n3?=?ListNode(6)
????n4?=?ListNode(9)
????n5?=?ListNode(12)
????m=n1
????n1.next=n2
????n2.next=n3
????n3.next=n4
????n4.next=n5
????print('原鏈表的節(jié)點：')????
????while?m:
????????print('節(jié)點%d的值:'%(m.val),m.val)
????????m=m.next
????print('\n排序之后的節(jié)點：')

????s=Solution()
????s.sortList(n1)
????while?n1:
????????print('節(jié)點%d的值:'%(n1.val),n1.val)
????????n1=n1.next
#result
原鏈表的節(jié)點：
節(jié)點4的值:?4
節(jié)點7的值:?7
節(jié)點6的值:?6
節(jié)點9的值:?9
節(jié)點12的值:?12

排序之后的節(jié)點：
節(jié)點4的值:?4
節(jié)點6的值:?6
節(jié)點7的值:?7
節(jié)點9的值:?9
節(jié)點12的值:?12

這個鏈表排序基于歸并排序算法。首先，遍歷整個鏈表，確定鏈表中元素個數(shù)，同時也可以確定鏈表的中間位置；然后從中間位置切斷鏈表(mid->key=NULL）；然后遞歸地給兩個鏈表進行排序；最后，合并兩個有序鏈表，形成一個完整的有序鏈表。整個算法的時間復雜度為O(n long)，空間復雜度為O(1)。

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

?

本文已收錄 GitHub，傳送門~^[1] ，里面更有大廠面試完整考點，歡迎 Star。

?

Reference