「@Author：Runsen」
❝
程式設計的本質來源于算法，而算法的本質來源于數學，程式設計隻不過将數學題進行代碼化。「---- Runsen」
❞
最近在重新梳理學算法的知識，本文為連結清單常見操作複習的總結文章，會講解常見的連結清單題目實作思路及附上答案，這些題目在leetcode上對應的題号也有給出，好好學習算法吧～
- 兩兩交換連結清單的節點
- 删除排序連結清單中的重複元素
- 排序連結清單（重要）
-
連結清單的中間結點
leetcode 對應題号：24，83，148，876
LeetCode 第24題：兩兩交換連結清單的節點
給定一個連結清單，兩兩交換其中相鄰的節點，并傳回交換後的連結清單。
示例:
給定 1->2->3->4, 你應該傳回 2->1->4->3. 1——2——3——4：我們需要做的就是，将一指向三，将二指向一，如此我們就完成了反轉，後續隻要一次周遊即可。
思路：a,b,pre記錄三個指針，相鄰兩個，相鄰兩個元素前面的一個，第一步将節點 2 指向節點 1，然後再将節點 1 指向節點三。這一步交換完畢後連結清單變為 2->1->3->4。在進行下一次交換，将節點 4 指向節點 3，節點3指向none 但是還要注意節點 1 的指向，節點 1 要指向節點 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題：删除排序連結清單中的重複元素
給定一個排序連結清單，删除所有重複的元素，使得每個元素隻出現一次。
示例 1:
輸入: 1->1->2
輸出: 1->2
示例 2:
輸入: 1->1->2->3->3
輸出: 1->2->3 由于輸入的清單已排序，是以我們可以通過将結點的值與它之後的結點進行比較來确定它是否為重複結點。如果它是重複的，我們更改目前結點的 next 指針，以便它跳過下一個結點并直接指向下一個結點之後的結點。
如果遇到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題：連結清單的中間結點（重要）
# 輸入：[1,2,3,4,5]
#輸出：此清單中的結點 3 (序列化形式：[3,4,5])
#傳回的結點值為 3 。 (測評系統對該結點序列化表述是 [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]
#輸出：此清單中的結點 4 (序列化形式：[4,5,6])
#由于該清單有兩個中間結點，值分别為 3 和 4，我們傳回第二個結點。
# 提示：
# 給定連結清單的結點數介于 1 和 100 之間。
# Related Topics 連結清單 「尋找連結清單的中間結點」
周遊兩次。第一次周遊求導連結清單長度，找出中間結點的長度值，第二層周遊找到中間結點并傳回；
快慢指針法。慢指針每次走一步，快指針每次走兩步，快指針走到連結清單末尾時，慢指針剛好走到連結清單中間。
「方法２時間複雜度更低，隻需周遊一次。」
# 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題：排序連結清單（重要）
在 時間複雜度和常數級空間複雜度下，對連結清單進行排序。
示例 1:
輸入: 4->2->1->3
輸出: 1->2->3->4
示例 2:
輸入: -1->5->3->4->0
輸出: -1->0->3->4->5 題目要求時間空間複雜度分别為和，根據時間複雜度我們自然想到二分法，進而聯想到歸并排序。歸并排序，後面細聊。
利用歸并的思想，遞歸地将目前連結清單分為兩段，然後merge，分兩段的方法是使用 fast-slow 法，用兩個指針，一個每次走兩步，一個走一步，直到快的走到了末尾，然後慢的所在位置就是中間位置，這樣就分成了兩段。
歸并排序分為兩步，
1.找到待排序連結清單的中間節點（使用快慢指針法，leetcode 876題）
2.合并兩個有序連結清單（leetcode 21題），是以本題相當于結合這兩步來實作連結清單排序。
# 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('原連結清單的節點：')
while m:
print('節點%d的值:'%(m.val),m.val)
m=m.next
print('\n排序之後的節點：')
s=Solution()
s.sortList(n1)
while n1:
print('節點%d的值:'%(n1.val),n1.val)
n1=n1.next
#result
原連結清單的節點：
節點4的值: 4
節點7的值: 7
節點6的值: 6
節點9的值: 9
節點12的值: 12
排序之後的節點：
節點4的值: 4
節點6的值: 6
節點7的值: 7
節點9的值: 9
節點12的值: 12 這個連結清單排序基于歸并排序算法。首先，周遊整個連結清單，确定連結清單中元素個數，同時也可以确定連結清單的中間位置；然後從中間位置切斷連結清單(mid->key=NULL）；然後遞歸地給兩個連結清單進行排序；最後，合并兩個有序連結清單，形成一個完整的有序連結清單。整個算法的時間複雜度為O(n long)，空間複雜度為O(1)。
「人生最重要的不是所站的位置，而是内心所朝的方向。隻要我在每篇博文中寫得自己體會，修煉身心；在每天的不斷重複學習中，耐住寂寞，練就真功，不畏艱難，奮勇前行，不忘初心，砥砺前行，人生定會有所收獲，不留遺憾 （作者：Runsen ）」
- END -
七十一、去重交換排序連結清單、 求連結清單的中間結點