python演算法-015將連結串列元素兩兩交換元素（交換值、就地翻轉）
大鵬一日同風起，扶搖直上九萬里。
假令風歇時下來，猶能簸卻滄溟水。
世人見我恆殊調，聞餘大言皆冷笑。
宣父猶能畏後生，丈夫未可輕年少。
——李白《上李邕》
在現代，別人對你的文章冷嘲熱諷，你來一句：“你行你上啊！”他可能就沒脾氣了。但是要換李白，他真的會上，因為他真的行！
題目描述：將連結串列的每兩個節點翻轉。不允許用新的節點。
例如：
給定連結串列Head->1->2->3->4->5->7->7->8
反轉為鏈Head->2->1->4->3->7->5->8->7
這題是為了明天的題目做 鋪墊 的，先來分析下這個題：本質上還是操作連結串列，之前我們做過類似的。不過，這次是翻轉節點，節點有兩個屬性data和next，交換兩個節點的值就可以完成了，這樣不需要將節點位置改變。這太簡單了，就像a=1,b=2,交換a,b的值一樣那麼簡單，只需要用一箇中間值tmp來儲存就行： tmp=a a=b b=tmp 。主要的問題就是如何遍歷的問題，這也是個不是問題的問題。用一個指標即可完成，但是對於明天的題，並沒有太大幫助。
下面來看利用next屬性，如何做：
利用next屬性必然會改變節點的位置，也就是連結串列結構會變，先來看看怎樣改變
主兩個指標，更好理解
圖中我用紅筆標出了操作順序1、2、3、4：先pre->fast，然後fast->slow，最後slow->next，這裡為什麼會先把next->fast.next:因為在第二步時，得儲存後面的連結串列，不然會丟失，這與a.b交換值是一個道理。這裡的順序也可以換成1、2、4、3，兩個效果是一樣的。
這裡有一個注意的地方就是每次的迴圈條件：宗旨就是當後面的節點不夠一組進行交換時，退出迴圈。但是如何知道後面不夠一組呢？先來看下程式碼。
下面程式碼實現：
def function(head): #判斷連結串列是否為空，為空返回 if head.next is None or head.next.next is None: return head pre=head # 指向slow的前驅節點 slow=head.next fast=slow.next #slow和fast為相鄰的節點 #next=fast.next # 這裡的迴圈條件要注意 # 連結串列的長度可能為奇數，也可能是偶數 # 每次四個指標會變換，因為是先操作再迭代下一組 # 再迭變換完後，如果fast指標後面只有一個元素，或者沒有元素，這時 # 後面的無法再進行翻轉，所以應該出迴圈，正常應該做完在判斷的， # 這裡只能符合的才操作，因為用的指標多了一個。 while fast.next is not None and fast.next.next is not None: next = fast.next #儲存連結串列，因為要斷開 pre.next=fast fast.next=slow slow.next=next # # 上面的四句做的操作，見圖 pre=slow slow=next fast=slow.next #因為面的判斷條件，最後一組，我們並沒有翻轉，這裡操作下 next = fast.next pre.next = fast fast.next = slow slow.next = next return head
這裡我用 while fast.next is not None and fast.next.next is not None ，這一句看起來很臃腫。
一組
這裡我用了四個指標，連結串列的長度可能為奇數，也可能是偶數，每次四個指標會變換，因為是先操作再迭代下一組，在變換完後，如果fast指標後面只有一個元素，或者沒有元素，這時後面的無法再進行翻轉，所以應該出迴圈，按分析應該做完在判斷的，但是因為涉及到一個next指標，每次都得確定還有next,才能操作，不然會報錯，這裡我還沒找到一個好的解釋辦法。 要注意的是，最後一組沒有換位置，可以把最後的四行語句註釋掉，看看結果就知道了。
image.png
鑑於此，我把指標減少了，只用一個主指標cur，用（cur，cur.next)這樣一組來代替slow，fast。
這樣的好處是，不用考慮fast是否有next.next,只看cur就行。操作是一樣的：
image.png
程式碼實現：
def function(head): if head is None or head.next is None: return head cur=head.next#當前遍歷節點 pre=head#當前遍歷節點的前驅節點 next=None#當前節點後繼節點的後繼節點 # 這裡的迴圈條件可能不太一樣，因為省掉了fast,所以考慮的東西就會變少。 while cur is not None and cur.next is not None: next=cur.next.next pre.next=cur.next #這裡可能一看不太好理解 # （cur.next).next # 這樣把cur.next看做一個節點，也就是之前的fast cur.next.next=cur cur.next=next pre=cur cur=next return head
迴圈條件變了，我將他們放在一個檔案裡了，如果後者沒問題，就可以 把變換的連結串列變回去：
if __name__ == '__main__':
head = creatLink(6)
print("head:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
head = function_1(head)
print("\nAfterReverse_1:") # 這是用slow和fast的
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
head = function_2(head) # 這是cur
print("\nAfterReverse_2:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
輸出結果：
image.png
全部程式碼：
import random
class LNode:
def __init__(self,arg):
self.data=arg
self.next=None
"""
題目描述：
給定連結串列Head->1->2->3->4->5->7->7->8
反轉為鏈Head->2->1->4->3->7->5->8->7
要求：
方法：只用一個cur,用pre和next輔助反轉。
"""
def creatLink(x):
i = 1
head = LNode(None)
tmp = None
cur = head
while i <= x:
n = random.randint(1, 9)
tmp = LNode(n)
cur.next = tmp
cur = tmp
i += 1
return head
#
#雙指標法
def function_1(head):
#判斷連結串列是否為空，為空返回
if head.next is None or head.next.next is None:
return head
pre=head # 指向slow的前驅節點
slow=head.next
fast=slow.next
#slow和fast為相鄰的節點
#next=fast.next
# 這裡的迴圈條件要注意
# 連結串列的長度可能為奇數，也可能是偶數
# 每次四個指標會變換，因為是先操作再迭代下一組
# 再迭變換完後，如果fast指標後面只有一個元素，或者沒有元素，這時
# 後面的無法再進行翻轉，所以應該出迴圈，正常應該做完在判斷的，
# 這裡只能符合的才操作，因為用的指標多了一個。
while fast.next is not None and fast.next.next is not None:
next = fast.next #儲存連結串列，因為要斷開
pre.next=fast
fast.next=slow
slow.next=next
# # 上面的四句做的操作，見圖
pre=slow
slow=next
fast=slow.next
#因為面的判斷條件，最後一組，我們並沒有翻轉，這裡操作下
next = fast.next
pre.next = fast
fast.next = slow
slow.next = next
return head
def function_2(head):
if head is None or head.next is None:
return head
cur=head.next#當前遍歷節點
pre=head#當前遍歷節點的前驅節點
next=None#當前節點後繼節點的後繼節點
# 這裡的迴圈條件可能不太一樣，因為省掉了fast,所以考慮的東西就會變少。
while cur is not None and cur.next is not None:
next=cur.next.next
pre.next=cur.next
#這裡可能一看不太好理解
# （cur.next).next
# 這樣把cur.next看做一個節點，也就是之前的fast
cur.next.next=cur
cur.next=next
pre=cur
cur=next
return head
if __name__ == '__main__':
head = creatLink(6)
print("head:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
head = function_1(head)
print("\nAfterReverse_1:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
head = function_2(head)
print("\nAfterReverse_2:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
鋪墊就到這裡，明天的題目是：
將連結串列以k個一組翻轉，不足k個也翻轉，
給定連結串列Head->1->2->3->4->5->7->7->8
k=3
反轉為鏈Head->3->2->1->7->5->4->8->7
會嗎？
今天就這樣，更多題目見 GitHub ,簡書、微信：DKider。
Data Knowledge idea(我故意打的r),這是我寒假想的名字，還挺好，之前沒有什麼實際意義，現在它有了！
我會盡量加快寫的速度，我還要留時間學其他的知識。加油吧！