iT邦幫忙

1

【leetcode練功坊】常見linked list操作技巧都都收在此了

哈囉,大家好,
今天我們要在leetcode上練功的主題是linked list,
linked list跟array有點像,
當資料常常需要搬動時,linked list就會比array來的快

這邊我們用python來做linked list的練習
題庫: Leetcode- Linked List

linked list 的定義:

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

反轉

linked list的一個經典問題是將linked list頭尾反轉,
如原本是1->2->3->4->5會變成5->4->3->2->1

題目: 206. Reverse Linked List
在python內的程式碼可以寫到非常簡潔:

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

題目: 92. Reverse Linked List II
題意: 與反轉整個linked list相比,只反轉指定範圍的位置
例子:

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: 
        # 先找到反轉的起點
        cur, head_last = head, None
        for i in range(m-1):
            cur, head_last = cur.next, cur
        
        # 反轉的邏輯做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
        if head_last:
            head_last.next = pre
        else:
            head = pre
        while pre and pre.next:
            pre=pre.next
        pre.next = cur
        return head

特別的小技巧

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

雖然這個技巧不在題目清單中,
但後續的題目很好用,也不太難

描述: 給定A, B兩個linked list,
節點分別為a1->a2->...->an
b1->b2->...->bn,
以A為頭,希望合併成a1->b1->a2->b2...->an->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

特殊規則重排

這邊收集一些將list按題目指定規則重排的問題

旋轉

題目: 61. Rotate List
題意: 將給定的linked list向右旋轉k步

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

我們可以先簡單實作一個「向右旋轉1步」的函數做k次,
然而要做一個技巧,由於旋轉「linked list的長度」次之後又回到原本的list,
故記得先取得linked list的長度避免重複運算

class Solution:
    
    # 向右旋轉一步
    def rotataOne(self, head):
        tail, tail_pre = head, None
        while tail and tail.next:
            tail, tail_pre = tail.next, tail
        tail_pre.next, tail.next  = None, head
        return tail
    
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next:
            return head
        
        # 先取得linked list的長度
        node, Len = head, 0
        while node:
            node, Len = node.next, Len+1
        
        for i in range(k % Len):
            head = self.rotataOne(head)
        return head

奇偶節點穿插

題目: 328. Odd Even Linked List
例子:

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:
        if not head:
            return head
        odd, even, even_head = head, head.next, head.next
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = even_head
        return head

相鄰節點兩兩交換

題目: 24. Swap Nodes in Pairs
例子:

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

這邊有一個很簡單的解,但不算真解,

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

因為題目說要真的交換node,不可以單純交換node裡的值
然而剛剛的「奇偶節點穿插」那道題不是可以將奇、偶位置的值抽離出來嗎?

技巧:
假設input是1->2->3->4->5->6->7->8,
首先,將奇、偶位置的節點形成兩個list
奇: 1->3->5->7
偶: 2->4->6->8

再將偶數節點的list當頭,
做「技巧: 按順序合併兩個長度相同的list」即可,
然而要處理一種特殊狀況:
若input的數字是奇數個如1->2->3->4->5->6->7,

奇: 1->3->5->7
偶: 2->4->6

將偶數節點的list當頭按順序合併會得到「2->1->4->3->6->5」,
奇數節點多出一個7,
需要適當修改程式處理

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        # 抽出奇、偶位置的節點形成兩個list
        odd, even = head, head.next
        odd_head, even_head = odd, even
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = None
        
        # merge
        A, B = even_head, odd_head
        head, tail = A, B
        while A:
            tail = B
            A.next, B.next, A, B = B, A.next, A.next, B.next
        tail.next = B
        return head

技巧: 尋找中間節點

題目: 876. Middle of the Linked List
題意: 給定一個非空的linked list,找出中間的節點
思路: 本題最單純的想法是掃兩遍list,第一遍先取得list的長度,
第二遍從head往前走長度的一半,
有沒有更簡潔的寫法呢?

想法是用快、慢指針,
慢的每次往前走一步,
快的每次往前走兩步,
快的走到尾巴時,
慢的就走到中間了,
程式細節:

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

綜合題: 重排list

本題可說是多個技巧的綜合運用
題目: 143. Reorder List
題意: 給定linked list L: L0→L1→…→Ln-1→Ln,重排為L0→Ln→L1→Ln-1→L2→Ln-2→…
例子:

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

思路: 本題共拆三個步驟做,這邊參考題解Python O(n) by two-pointers [w/ Visualization]的圖示

第一步: 找出list的中間節點(注意這邊找的中間節點跟上一題相比,找在前一個節點,本例為2號節點)
https://ithelp.ithome.com.tw/upload/images/20200822/20117114HTRz4fJKKF.png

第二步: 將後半段list反轉
https://ithelp.ithome.com.tw/upload/images/20200822/20117114Xoobp7gqwr.png

第三步: 將兩個list按順序合併
https://ithelp.ithome.com.tw/upload/images/20200822/201171146q2Cqenq2T.png

程式:

class Solution:
    def reorderList(self, head: ListNode) -> None:
        #step 1: find middle
        if not head or not head.next: 
            return
        slow, fast = head, head
        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
        A, B = head, pre
        head = A
        while B:
            A.next, B.next, A, B = B, A.next, A.next, B.next

linked list的排序

排序系列的問題感覺很有技巧性,放到後面解說

合併兩個排序過的linked list

題目: 21. Merge Two Sorted Lists
例子:

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

技巧: 宣告一個節點為負無限大,然後看哪個list的節點小就接上去
程式:

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

題目: 148. Sort List
題意: 本題要求對一個未排序的linked list用O(nlogn)的時間排序
思路: merge sort,先找到list的中間,各自對前後兩個list排序,再套用上題merge

程式:

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        middle = self.middleNode(head)
        nextToMiddle = middle.next
        middle.next = None
        
        left = self.sortList(head)
        right = self.sortList(nextToMiddle)
        return self.mergeTwoLists(left, right)

    def middleNode(self, head: ListNode) -> ListNode:
        slow, fast = head, head
        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

合併k個排序過的linked list

題目: 23. Merge k Sorted Lists
這一題乍看之下你會覺得難易度編排很怪,上一題合併2個排序過的linked list是easy,
怎麼合併k個排序過的linked list就變成hard了?

這一題應該是難在時間複雜度要如何做的夠快,
假設有k個linked list,全部有N個節點,
一步步合併的方法(合併k-1次到第一個list)大約要O(kN)的時間

<一步步合併法,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

然而若使用Divide And Conquer,分而治之法,
時間複雜度可降到O(N*log k)

圖示: (可於leetcode上看解答)
https://ithelp.ithome.com.tw/upload/images/20200822/20117114OQAyiIlLVd.png

<分而治之法,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

尚未有邦友留言

立即登入留言