每天都要刷幾題leetcode

看到了大神的代碼，毫不猶豫拷貝下來

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = Noneclass Solution(object):"""原理：首先初始化快指針 fast = head.next.next 和 slow = head.next，此時快指針走的路長為2, m慢指針走的路長為1，之后令快指針每次走兩步，慢指針每次走一步，這樣快指針走的路長始終是慢指針走的路長的兩倍，若不存在環，直接返回None，若存在環，則 fast 與 slow 肯定會在若干步之后相遇；性質1：設從head需要走 a 步到達環的入口，如果環存在的話，再走 b 步可以再次到達該入口（即環的長度為b），如果存在環的話，上述描述的 快指針 fast 和 慢指針slow 必然會相遇，且此時slow走的路長小于 a + b(可以自行證明)，設其為 a + x，當快慢指針相遇時，快指針已經至少走完一圈環了，不妨設相遇時走了完整的m圈(m >= 1)，有：快指針走的路長為 a + mb + x慢指針走的路長為 a + x由于快指針fast 走的路長始終是慢指針的 2倍，所以：a + mb + x = 2(a + x)化簡可得：a = mb - x ------------- (*)當快指針與慢指針相遇時，由于 <性質1> 的存在，可以在鏈表的開頭初始化一個新的指針，稱其為 detection, 此時 detection 距離環的入口的距離為 a，此時令 detection 和 fast 每次走一步，會發現當各自走了 a 步之后，兩個指針同時到達了環的入口，理由分別如下：detection不用說了，走了a步肯定到剛好到入口fast已經走過的距離為 a + mb + x，當再走 a 步之后，fast走過的總距離為 2a + mb + x，帶入性質1的(*)式可得：2a + mb + x = a + 2mb，會發現，fast此時剛好走完了整整 2m 圈環，正好處于入口的位置?；诖?#xff0c;我們可以進行循環，直到 detection 和 fast 指向同一個對象，此時指向的對象恰好為環的入口。"""def detectCycle(self, head):""":type head: ListNode:rtype: ListNode"""# 首先初始化快指針和慢指針，確保快指針走的路的長度是慢指針長度的2倍if head and head.next:fast = head.next.nextslow = head.nextelse:return None # 說明無環# 進行循環，首先讓快指針和慢指針第一次相遇while fast:if fast != slow:# 快指針走兩步if fast.next:fast = fast.next.nextelse:return None # 說明無環# 慢指針走一步slow = slow.nextelse:detection = headwhile detection != slow: # 此時由于slow和fast是一樣的，用哪個都行slow = slow.nextdetection = detection.nextreturn detection

---

我這個垃圾

class Solution(object):def detectCycle(self, head):""":type head: ListNode:rtype: ListNode"""l = []while head and head not in l:l.append(head)head = head.nextreturn head

**

# 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 head is None or head.next is None:return#快慢指針找到鏈表中點sf = s = headwhile f and f.next:s = s.nextf = f.next.next#中點之后的鏈表反轉p = c = sn = c.nextwhile n:p = cc = nn = n.nextc.next = p#c為末尾節點，雙指針分別從頭結點和末尾節點重構鏈表n1 = h1 = headn2 = h2 = cwhile h1 != h2 and h1.next != h2:n1 = h1.nextn2 = h2.nexth1.next = h2h2.next = n1h1 = n1h2 = n2h2.next = None

---

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = Noneclass Solution(object):def reorderList(self, head):if not head or not head.next: return L = []while head:L.append(head)head = head.nextfor i in range(len(L)//2):L[i].next = L[len(L)-i-1]L[len(L)-i-1].next = L[i+1] L[i+1].next = None

總結

以上是生活随笔為你收集整理的leetcode 刷题142 143的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。