Leetcode之旅|大珠小珠落玉盤（鏈表反轉節點）

02-12

圖片來源，侵刪

　　這篇博客寫於腰受傷後卧病在床期間~~~

　　當時興緻勃勃地去健身，想著為科學奮鬥七十年，真是幹勁十足呀~~又是空中瑜伽，又是哈他瑜伽，每種都開心地去嘗試，然而，堅持了三天後，被一個愛diss人的普拉提教練給push，然後很悲劇地把腰給傷了。只能寫博客聊以慰藉。。。。

題目描述

　　今天寫的這道題和之前反轉k個節點的這道有點類似,即：對一個已知鏈表： $L_0→L_1→…→L_{n-1}→L_n$ ,改變其鏈接順序為： $L_0→L_n→L_1→L_{n-1}→L_2→L_{n-2}→…$ 。即第一個後為最後一個，接著是第二個，接著是倒數第二個...比如原鏈表為{1,2,3,4},修改後變為{1,4,2,3}。要求是原位修改，即不能改變原節點的值，只改變它們之間的先後順序，也不需要返回任何值。
　　

解題思路

　　說實話，這道題我拿到手的時候基本沒思路，因為鏈表這種數據結構的特殊性導致我們既無法通過下標直接訪問某個節點，也無法知道某個節點的前驅節點。後來看一些帖子說這個問題是反轉節點這道題的延伸，就有了想法。

　　我們不妨把鏈表看作一根均勻分布珠子的項鏈，然後讓它對摺，這樣第一顆珠子會和最後一顆珠子對應，第二顆會和倒數第二顆對應，以此類推。這樣一來，我們同步地遍歷這兩段繩子，不就可以按照要求綴出新的項鏈了嗎？

　　所以問題就可以這麼解決：我們將鏈表從中間分開，將後面那半反轉，然後將兩部分逐個拼接。這會用到我們常用的兩個套路：找到中間位置和鏈表的反轉。第一個套路就是熟悉的slow-fast指針法，即設置slow和fast兩個指針，slow每次走一步，fast每次走兩步，這樣當fast到達終點時，slow會走一半到中間。根據需求可以對slow和fast進行初始化，比如slow=fast=head，或者slow=head,fast=head.next。第二個套路也很熟悉，即對每個節點保存其Pre和next，將其對調即可，而且因為是逐個反轉，pre,cur,next會逐個後移，前驅與後繼信息得以在循環中傳遞。

　　雖然這樣，我們可能還會有一個問題：如果珠子是奇數個怎麼辦？這個好解決，因為奇數個珠子的項鏈肯定存在最中間的一顆，而這顆肯定會放在最後，我們只要將這顆珠子放在後半部分的第一個，這樣後半部分反轉後它即為這一半的最後一顆，在拼接時，由於後半部分晚於前半部分，所以這顆珠子肯定會是最後一個。

　　代碼如下：

代碼

# Definition for singly-linked list.# class ListNode(object):# def __init__(self, x):# self.val = x# self.next = Noneclass Solution(object): def reorderList(self, head): """ :type head: ListNode :rtype: void Do not return anything, modify head in-place instead. """ if not head or not head.next: return # 套路一：通過slow和fast兩個指針找到中心節點 slow = head fast = head.next while fast and fast.next: slow = slow.next fast = fast.next.next # 將鏈表以最中心的節點為分界線，劃分為兩個鏈表 # 前面的一半為鏈表1，後面的鏈表為鏈表2 # 套路二：將鏈表2反向 pre2 = slow head2 = slow.next slow.next = None while(head2.next): _next = head2.next head2.next = pre2 pre2 = head2 head2 = _next # 將鏈表1和反向後的鏈表2逐個節點地拼接起來， # 還原出一個完整的鏈表 head2.next = pre2 head1 = head while head1 and head2: tmp1 = head1.next tmp2 = head2.next head1.next = head2 head2.next = tmp1 head2 = tmp2 head1 = tmp1 return

總結

　　雖然沒有都更新到博客里，但鏈表這個主題的題目已經基本告一段落了，下一步是tree，已經被遞歸給虐慘。後面的鏈表的相關題目應該還是會找機會更新，免得自己忘記。