1

``````# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
``````

# 反轉

``````class Solution:
def reverseList(self, head: ListNode) -> ListNode:
while cur:
cur.next, cur, pre = pre, cur.next, cur
return pre
``````

``````Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
(測資保證 1 ≤ m ≤ n ≤ list的長度)
``````

``````class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
# 先找到反轉的起點
for i in range(m-1):

# 反轉的邏輯做n-m+1次，pre會變成新的頭
pre = None
for _ in range(n-m+1):
cur.next, cur, pre = pre, cur.next, cur

# 將list前後串好
# e.g. input 1->[2->3->4]->5->NULL, m = 2, n = 4
# 中間反轉變[4->3->2]，前後串好變1->4->3->2->5
else:
while pre and pre.next:
pre=pre.next
pre.next = cur
``````

# 特別的小技巧

## 技巧: 按順序合併兩個長度相同的list

b1->b2->...->bn，

(A的長度可以多1，變a1->b1->a2->b2...->an->bn->a{n+1})

``````head = A
while B:
A.next, B.next, A, B = B, A.next, A.next, B.next
``````

# 特殊規則重排

## 旋轉

``````Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
``````

``````class Solution:

# 向右旋轉一步
while tail and tail.next:
tail, tail_pre = tail.next, tail
return tail

def rotateRight(self, head: ListNode, k: int) -> ListNode:

while node:
node, Len = node.next, Len+1

for i in range(k % Len):
``````

## 奇偶節點穿插

``````Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL
``````

``````class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
``````

## 相鄰節點兩兩交換

``````Input:  1->2->3->4
Output: 2->1->4->3
``````

``````class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
while node and node.next:
node.val,node.next.val=node.next.val,node.val
node=node.next.next
``````

``````class Solution:
def swapPairs(self, head: ListNode) -> ListNode:

# 抽出奇、偶位置的節點形成兩個list
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = None

# merge
while A:
tail = B
A.next, B.next, A, B = B, A.next, A.next, B.next
tail.next = B
``````

## 技巧: 尋找中間節點

``````class Solution:
def middleNode(self, head: ListNode) -> ListNode:
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
``````

## 綜合題: 重排list

``````Input:  1->2->3->4->5
Output: 1->5->2->4->3
``````

``````class Solution:
def reorderList(self, head: ListNode) -> None:
#step 1: find middle
return
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next

#step 2: reverse second half
cur, pre = slow.next, None
while cur:
cur.next, cur, pre = pre, cur.next, cur
slow.next = None

#step 3: merge lists
while B:
A.next, B.next, A, B = B, A.next, A.next, B.next
``````

``````Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
``````

``````class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1

res = ListNode(float('-inf'))
cur = res
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return res.next
``````

## merge sort

``````class Solution:
def sortList(self, head: ListNode) -> ListNode:
nextToMiddle = middle.next
middle.next = None

right = self.sortList(nextToMiddle)
return self.mergeTwoLists(left, right)

def middleNode(self, head: ListNode) -> ListNode:
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1

res = ListNode(float('-inf'))
cur = res
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return res.next
``````

<一步步合併法，4628ms>

``````class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:
return None
res = lists[0]
for i in range(1, len(lists)):
res = self.mergeTwoLists(res, lists[i])
return res

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1

res = ListNode(float('-inf'))
cur = res
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return res.next
``````

<分而治之法，124ms>

``````class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:
return None
k, interval = len(lists), 1
while interval < k:
for i in range(0, k - interval, interval * 2):
lists[i] = self.mergeTwoLists(lists[i], lists[i + interval])
interval *= 2
return lists[0]

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1

res = ListNode(float('-inf'))
cur = res
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return res.next
``````