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

玩轉演算法面試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
輸出: 5->4->3->2->1->NULL

進階:

你可以迭代或遞迴地反轉連結串列。你能否用兩種方法解決這道題?


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
兩個指標,一個記錄當前的頭節點,一個記錄將要成為頭節點的節點
if not head:
return None        
cur = head
nex = head.next        
while nex:
head.next = nex.next
nex.next = cur
cur = nex
nex = head.next
return cur
時間O(n),空間O(1)
"""
prev = None
while head:
curr = head
head = head.next
curr.next = prev
prev = curr
return prev

92. 反轉連結串列 II

反轉從位置 m 到 n 的連結串列。請使用一趟掃描完成反轉。

說明:
1 ≤ m ≤ n ≤ 連結串列長度。

示例:

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

class Solution:
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
思路:首先移動到指定位置,然後與反轉連結串列I類似
"""     
if head == None or head.next == None or m >= n or m < 0 or n < 0:
return head
dummyNode = ListNode(0)
p = dummyNode
q = head
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->1->2
輸出: 1->2

示例 2:

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """   
        if head == None or head.next == None:
            return head
        cur = head
        while cur.next:
            if cur.next.val == cur.val:
                cur.next = cur.next.next #跳過重複節點
            else:
                cur = cur.next #當前節點沒有重複,移動到下一個
        return head

86. 分隔連結串列

給定一個連結串列和一個特定值 x,對連結串列進行分隔,使得所有小於 x 的節點都在大於或等於 x 的節點之前。

你應當保留兩個分割槽中每個節點的初始相對位置。

示例:

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
head1 = ListNode(0)#新的頭結點,用於存放小於x的數
head2 = ListNode(0)#新的頭結點,用於存放大於等於x的數
p1 = head1
p2 = head2       
curr = head
while curr:
if curr.val < x:#前半段,頭節點head1, p不斷移動 
p1.next = curr
curr = curr.next
p1 = p1.next
p1.next = None
else:#前半段,頭節點head2, q不斷移動  
p2.next = curr
curr = curr.next
p2 = p2.next
p2.next = None
#兩半段拼接起來  
p1.next = head2.next
head = head1.next
return head 

328. 奇偶連結串列

給定一個單連結串列,把所有的奇數節點和偶數節點分別排在一起。請注意,這裡的奇數節點和偶數節點指的是節點編號的奇偶性,而不是節點的值的奇偶性。

請嘗試使用原地演算法完成。你的演算法的空間複雜度應為 O(1),時間複雜度應為 O(nodes),nodes 為節點總數。

示例 1:

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

示例 2:

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

說明:

  • 應當保持奇數節點和偶數節點的相對順序。
  • 連結串列的第一個節點視為奇數節點,第二個節點視為偶數節點,以此類推。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
def oddEvenList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None or head.next == None:
return head
odd = head
even = head.next
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
return head

 

2. 兩數相加

 

給定兩個非空連結串列來表示兩個非負整數。位數按照逆序方式儲存,它們的每個節點只儲存單個數字。將兩數相加返回一個新的連結串列。

你可以假設除了數字 0 之外,這兩個數字都不會以零開頭。

示例:

輸入:(2 -> 4 -> 3)   (5 -> 6 -> 4)
輸出:7 -> 0 -> 8
原因:342   465 = 807

 


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
dummy = head = ListNode(0)
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)
return head.next

 

445. 兩數相加 II

 

給定兩個非空連結串列來代表兩個非負整數。數字最高位位於連結串列開始位置。它們的每個節點只儲存單個數字。將這兩數相加會返回一個新的連結串列。

你可以假設除了數字 0 之外,這兩個數字都不會以零開頭。

進階:

如果輸入連結串列不能修改該如何處理?換句話說,你不能對列表中的節點進行翻轉。

示例:

輸入: (7 -> 2 -> 4 -> 3)   (5 -> 6 -> 4)
輸出: 7 -> 8 -> 0 -> 7

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
def addTwoNumbers(self, l1, l2):
"""
: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
head = ListNode(0)
cur = head
for st in str(num):
temp = ListNode(int(st))  
cur.next = temp  
cur = temp  
return head.next

 

虛擬頭結點:

 

 

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

刪除連結串列中等於給定值 val 的所有節點。

示例:

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

 


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
dummy_head = ListNode(-1)
dummy_head.next = head
pre = dummy_head
while pre.next is not None:
if pre.next.val == val:
pre.next = pre.next.next
else:
pre = pre.next
return dummy_head.next

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

給定一個排序連結串列,刪除所有含有重複數字的節點,只保留原始連結串列中 沒有重複出現 的數字。

示例 1:

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

示例 2:

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

 


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head;
dummy_head = ListNode(-1)
dummy_head.next = head
pre = dummy_head
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                
return dummy_head.next

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

將兩個有序連結串列合併為一個新的有序連結串列並返回。新連結串列是通過拼接給定的兩個連結串列的所有節點組成的。 

示例:

輸入:1->2->4, 1->3->4
輸出:1->1->2->3->4->4

# Definition for singly-linked list.
# 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
dummy_head = ListNode(0)
cur = dummy_head
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
return dummy_head.next

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

給定一個連結串列,兩兩交換其中相鄰的節點,並返回交換後的連結串列。

示例:

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

說明:

  • 你的演算法只能使用常數的額外空間。
  • 你不能只是單純的改變節點內部的值,而是需要實際的進行節點交換。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
        if head is None:
            return None
        dummy_head = ListNode(0)
        dummy_head.next = head
        head = dummy_head
        
        while head.next != None and head.next.next != None:
            n1 = head.next
            n2 = head.next.next
            # head->n1->n2->...      => head->n2->n1->...
            head.next = n2
            n1.next = n2.next
            n2.next = n1
            #move to next pair 
            head = n1
        return dummy_head.next

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

給出一個連結串列,每 個節點一組進行翻轉,並返回翻轉後的連結串列。

是一個正整數,它的值小於或等於連結串列的長度。如果節點總數不是 的整數倍,那麼將最後剩餘節點保持原有順序。

示例 :

給定這個連結串列:1->2->3->4->5

當 = 2 時,應當返回: 2->1->4->3->5

當 = 3 時,應當返回: 3->2->1->4->5

說明 :

  • 你的演算法只能使用常數的額外空間。
  • 你不能只是單純的改變節點內部的值,而是需要實際的進行節點交換。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if not head or not head.next or k < 2:
return head
dummy = ListNode(-1)
dummy.next = head
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. 重複直到所有輸入資料插入完為止。 

示例 1:

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

示例 2:

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
def insertionSortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
p = dummy_head = ListNode(0)
cur = dummy_head.next = head
while cur and cur.next:
val = cur.next.val
if cur.val < val:
cur = cur.next
continue
if p.next.val > val:
p = dummy_head
#val如果比當前已排序的最小值小,不執行,如果大,移動p到要插入的節點處
while p.next.val < val :
p = p.next
t = cur.next
cur.next = t.next
t.next = p.next
p.next = t
return dummy_head.next

148. 排序連結串列

在 O(n log n) 時間複雜度和常數級空間複雜度下,對連結串列進行排序。

示例 1:

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

示例 2:

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
#時間O(2n),空間O(n) or O(1)?
cur = head
res = []
while cur:
res.append(cur.val)
cur = cur.next
res.sort()
new_cur = head
for i in res:
new_cur.val = i
new_cur = new_cur.next
return head

歸併  法二:


        #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
def sortList(self, head):
if not head or not head.next:
return head
pre, slow, fast = None, head, head
while fast and fast.next:
pre, slow, fast = slow, slow.next, fast.next.next
pre.next = None
return self.merge(self.sortList(head), self.sortList(slow))