328. 奇偶鏈表
給定一個單鏈表熄浓，把所有的奇數(shù)節(jié)點和偶數(shù)節(jié)點分別排在一起舅踪。請注意界阁，這里的奇數(shù)節(jié)點和偶數(shù)節(jié)點指的是節(jié)點編號的奇偶性萍倡，而不是節(jié)點的值的奇偶性楼咳。
請嘗試使用原地算法完成食寡。你的算法的空間復雜度應為 O(1)雾狈，時間復雜度應為 O(nodes)，nodes 為節(jié)點總數(shù)抵皱。
示例 1:
輸入: 1->2->3->4->5->NULL
輸出: 1->3->5->2->4->NULL
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
# 邊界條件判定
if not head or not head.next or not head.next.next:
return head
# 奇數(shù)頭節(jié)點
jishu = head
isjishu = True # 標記奇數(shù)位
# 先保存偶數(shù)頭節(jié)點
oushu0 = head.next
# 偶數(shù)頭節(jié)點
oushu = head.next
cur = head.next.next
while cur:
# 先把相鄰的奇數(shù)位善榛、偶數(shù)位鏈表挑選出來
if isjishu:
jishu.next = cur
jishu = cur
else:
oushu.next = cur
oushu = cur
# 用于判斷奇數(shù)位是否結束
isjishu = not isjishu
cur = cur.next
# 最后將奇數(shù)位鏈表的最后一個節(jié)點與偶數(shù)位鏈表的頭節(jié)點相連
jishu.next = oushu0
# 偶數(shù)位鏈表最后一位與空相連
oushu.next = None
return head
234. 回文鏈表
輸入：head = [1,2,2,1]
輸出：true
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
# 輔助數(shù)據(jù)按順序存儲鏈表元素
items = []
cur = head
while cur:
items.append(cur.val)
cur = cur.next
return items == items[::-1]
61. 旋轉(zhuǎn)鏈表
輸入：head = [1,2,3,4,5], k = 2
輸出：[4,5,1,2,3]
解釋：[1,2,3,4,5]==>[5,1,2,3,4]==>[4,5,1,2,3]
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head or not head.next or k == 0:
return head
# 把尾部的k個節(jié)點放在最前面
# 鏈表長度
count = 1
cur = head
while cur.next:
count += 1
cur = cur.next
# 反向鏈接
cur.next = head
# 旋轉(zhuǎn)次數(shù),前t個鏈表移動到后面
t = count - k % count
while t > 0:
cur = cur.next
t -= 1
# 新的頭節(jié)點
newhead = cur.next
# 斷開節(jié)點
cur.next = None
return newhead
19. 刪除鏈表的倒數(shù)第 N 個結點
輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
# 雙指針
dummy = ListNode(0,head) # 啞結點
slow = dummy
fast = head
for i in range(n): # slow和fast中間相隔兩個 n 個結點
fast = fast.next
while fast is not None: # 當fast到達末尾，slow所指的下一個節(jié)點將被刪除
slow = slow.next
fast = fast.next
# 刪除節(jié)點元素
slow.next = slow.next.next
return dummy.next
876. 鏈表的中間結點
給定一個頭結點為 head 的非空單鏈表呻畸，返回鏈表的中間結點移盆。
如果有兩個中間結點，則返回第二個中間結點伤为。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# 使用快慢指針
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
# 1 使用輔助數(shù)組
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
l = [head]
while l[-1].next:
l.append(l[-1].next)
return l[len(l)//2]
# 2 先獲取鏈表的長度n咒循，之后遍歷到 n//2為止
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
n = 0
tmpnode = head
while tmpnode:
tmpnode = tmpnode.next
n += 1
i = 0
cur = head
while i < n//2:
cur = cur.next
i += 1
return cur
141. 環(huán)形鏈表
給你一個鏈表的頭節(jié)點 head ，判斷鏈表中是否有環(huán)绞愚。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# 方法1：使用一個哈希表
# 思路：使用一個哈希表來存儲所有已經(jīng)訪問過的節(jié)點叙甸，如果該節(jié)點存在于哈希表中，則說明該鏈表是環(huán)形鏈表
class Solution:
def hasCycle(self, head: ListNode) -> bool:
seen = set()
while head:
if head in seen:
return True
seen.add(head)
head = head.next
return False
# # 方法2：快慢指針
# # 思路：快指針每次移動一步位衩，慢指針每次移動兩步裆蒸，如果快指針追上慢指針，則為環(huán)形鏈表
class Solution:
def hasCycle(self, head: ListNode) -> bool:
# 邊界條件
if head == None or head.next == None:
return False
# 快慢指針
slow = head
fast = head.next
while slow != fast:
if fast == None or fast.next == None:
return False
slow = slow.next # 每次走一步
fast = fast.next.next # 每次走兩步
return True
21. 合并兩個有序鏈表
輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
prevHead = ListNode(-1)
prev = prevHead
while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
if l1 is not None:
prev.next = l1
else:
prev.next = l2
return prevHead.next
142. 環(huán)形鏈表 II
輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)糖驴，其尾部連接到第二個節(jié)點僚祷。
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow = head
fast = head
while True:
if fast == None or fast.next == None:
return None
slow = slow.next
fast = fast.next.next
if slow == fast:
break
ans = head
while ans != slow:
ans = ans.next
slow = slow.next
return ans
160. 相交鏈表
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8'
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
# 思路：采用雙指針，分別指向兩鏈表的頭節(jié)點
# 指針A先遍歷完鏈表headA,再開始遍歷headB
# 指針B先遍歷完鏈表headB,再開始遍歷headA
A, B = headA, headB
while A != B:
A = A.next if A else headB
B = B.next if B else headA
return A
