# 玩轉演算法面試LeetCode演算法練習——在連結串列穿針引線

206. 反轉連結串列

92. 反轉連結串列 II

83. 刪除排序連結串列中的重複元素

86. 分隔連結串列

328. 奇偶連結串列

2. 兩數相加

445. 兩數相加 II

203. 刪除連結串列中的節點

82. 刪除排序連結串列中的重複元素 II

21. 合併兩個有序連結串列

24. 兩兩交換連結串列中的節點

25. k個一組翻轉連結串列

147. 對連結串列進行插入排序

148. 排序連結串列

# 206. 反轉連結串列

``````輸入: 1->2->3->4->5->NULL

``````
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
"""
:rtype: ListNode

return None
while nex:
nex.next = cur
cur = nex
return cur

"""
prev = None
curr.next = prev
prev = curr
return prev``````

# 92. 反轉連結串列 II

1 ≤ m ≤ n ≤ 連結串列長度。

``````輸入: 1->2->3->4->5->NULL, m = 2, n = 4

``````
class Solution:
"""
:type m: int
:type n: int
:rtype: ListNode

"""
if head == None or head.next == None or m >= n or m < 0 or n < 0:
dummyNode = ListNode(0)
p = dummyNode
for x in range(1,m):
p.next = q
q = q.next
p = p.next
start = None
end = q
nex = None
for x in range(m, n   1):
nex = q.next
q.next = start
start = q
q = nex
p.next = start
end.next = nex
return dummyNode.next``````

# 83. 刪除排序連結串列中的重複元素

``````輸入: 1->1->2

``````

``````輸入: 1->1->2->3->3

``````
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
"""
:rtype: ListNode
"""
while cur.next:
if cur.next.val == cur.val:
cur.next = cur.next.next #跳過重複節點
else:
cur = cur.next #當前節點沒有重複，移動到下一個

# 86. 分隔連結串列

``````輸入: head = 1->4->3->2->5->2, x = 3

``````
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
"""
:type x: int
:rtype: ListNode
"""
while curr:
p1.next = curr
curr = curr.next
p1 = p1.next
p1.next = None
p2.next = curr
curr = curr.next
p2 = p2.next
p2.next = None
#兩半段拼接起來

# 328. 奇偶連結串列

``````輸入: 1->2->3->4->5->NULL

``````

``````輸入: 2->1->3->5->6->4->7->NULL

• 應當保持奇數節點和偶數節點的相對順序。
• 連結串列的第一個節點視為奇數節點，第二個節點視為偶數節點，以此類推。
``````
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
"""
:rtype: ListNode
"""
t = even
while even != None and even.next != None :
odd.next = even.next    #2 1->3->5->6->4->7     odd->2 even->1
#|____^
odd = odd.next          #2 1->3->5->6->4->7     odd->3 even->1
#|____^
even.next = odd.next    #2->3->5->6->4->7     odd->2 even->1
#   1——^
even = even.next        #2->3->5->6->4->7     odd->2 even->5
#   1——^
odd.next = t

# 2. 兩數相加

``````輸入：(2 -> 4 -> 3)   (5 -> 6 -> 4)

``````
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
carry = 0
while l1 or l2:
v1 = 0 if l1 is None else l1.val
v2 = 0 if l2 is None else l2.val
result = (v1   v2   carry) % 10
carry = (v1   v2   carry) // 10
dummy.next = ListNode(result)
dummy = dummy.next
l1 = None if l1 is None else l1.next
l2 = None if l2 is None else l2.next
if carry > 0:
dummy.next = ListNode(carry)

# 445. 兩數相加 II

``````輸入: (7 -> 2 -> 4 -> 3)   (5 -> 6 -> 4)

``````
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
num1,num2 = 0,0
while l1:
num1 = num1 * 10   l1.val
l1 = l1.next
while l2:
num2 = num2 * 10   l2.val
l2 = l2.next
num = num1   num2
for st in str(num):
temp = ListNode(int(st))
cur.next = temp
cur = temp

# 203. 刪除連結串列中的節點

``````輸入: 1->2->6->3->4->5->6, val = 6

``````
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
"""
:type val: int
:rtype: ListNode
"""
while pre.next is not None:
if pre.next.val == val:
pre.next = pre.next.next
else:
pre = pre.next

# 82. 刪除排序連結串列中的重複元素 II

``````輸入: 1->2->3->3->4->4->5

``````

``````輸入: 1->1->1->2->3

``````
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
"""
:rtype: ListNode
"""
while pre.next is not None:
cur = pre.next
while cur.next and cur.val ==  cur.next.val :
cur = cur.next
if cur != pre.next:#if 連結串列的指向不同....
pre.next = cur.next
else:
pre = pre.next

# 21. 合併兩個有序連結串列

``````輸入：1->2->4, 1->3->4

``````
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if l1==None:
return l2
if l2==None:
return l1
while l1 and l2:#不用or的原因是當某個連結串列空了之後，.val報錯
if l1.val < l2.val:
cur.next = ListNode(l1.val)
l1 = l1.next
else:
cur.next = ListNode(l2.val)
l2 = l2.next
cur = cur.next
cur.next = l1 if l2 is None else l2

# 24. 兩兩交換連結串列中的節點

`給定 `1->2->3->4`, 你應該返回 `2->1->4->3`.`

• 你的演算法只能使用常數的額外空間。
• 你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。
``````
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
"""
:rtype: ListNode
"""
return None

n1.next = n2.next
n2.next = n1
#move to next pair

# 25. k個一組翻轉連結串列

• 你的演算法只能使用常數的額外空間。
• 你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。
``````
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
"""
:type k: int
:rtype: ListNode
"""
dummy = ListNode(-1)
pre = dummy
cur = pre
#計算連結串列長度
num = 0
while cur.next:
num  = 1
cur = cur.next
#畫圖理解
while num >= k:
cur = pre.next
for i in range(1,k):
t = cur.next
cur.next = t.next
t.next = pre.next
pre.next = t
pre = cur
num -= k
return dummy.next``````

# 147. 對連結串列進行插入排序

1. 插入排序是迭代的，每次只移動一個元素，直到所有元素可以形成一個有序的輸出列表。
2. 每次迭代中，插入排序只從輸入資料中移除一個待排序的元素，找到它在序列中適當的位置，並將其插入。
3. 重複直到所有輸入資料插入完為止。

``````輸入: 4->2->1->3

``````

``````輸入: -1->5->3->4->0

``````
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
"""
:rtype: ListNode
"""
while cur and cur.next:
val = cur.next.val
if cur.val < val:
cur = cur.next
continue
if p.next.val > val:
#val如果比當前已排序的最小值小，不執行，如果大，移動p到要插入的節點處
while p.next.val < val :
p = p.next
t = cur.next
cur.next = t.next
t.next = p.next
p.next = t

# 148. 排序連結串列

``````輸入: 4->2->1->3

``````

``````輸入: -1->5->3->4->0

``````
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
"""
:rtype: ListNode
"""
#時間O(2n)，空間O(n) or O(1)?
res = []
while cur:
res.append(cur.val)
cur = cur.next
res.sort()
for i in res:
new_cur.val = i
new_cur = new_cur.next

``````
#O(nlogn)
def merge(self, h1, h2):
dummy = tail = ListNode(None)
while h1 and h2:
if h1.val < h2.val:
tail.next,tail,h1 = h1,h1,h1.next
else:
tail.next,tail,h2 = h2,h2,h2.next
tail.next = h1 or h2
return dummy.next