# [資演] Linked list 練習

###### tags: `資演`

* [刪除 linked list 最中間的節點](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
給定一個 linked list 的 `head`，把這個 list 的最中間那個節點刪除掉，並回傳那個新的 list 的 `head`。
:::spoiler 解答
這題只要使用兩個指針的技巧就可以輕鬆解決。

    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution(object):
        def deleteMiddle(self, head):
            """
            :type head: Optional[ListNode]
            :rtype: Optional[ListNode]
            """
            if head.next is None:
                return None
                
            slow = head
            fast = head.next.next

            while (fast != None and fast.next != None):
                fast = fast.next.next
                slow = slow.next

            # tmp = slow.next
            slow.next = slow.next.next
            # del tmp

            return head
                

:::
* [旋轉 linked list](https://leetcode.com/problems/rotate-list/)
給定一個 linked list 的`head`以及一個整數`k`，把這個 list 向後旋轉`k`格。
:::spoiler 解答
這種牽涉到旋轉的問題，我們可以先遍歷一次list（順便算list的長度），把`tail`連接到`head`，也就是說，把原始的linked list變成一個circular linked list。

    class Solution(object):
        def rotateRight(self, head, k):
            if not head or not head.next:
                return head
                
            curr = head
            len = 1
            
            while curr.next:
                curr = curr.next
                len += 1
                
            curr.next = head
            k = k % len

            for i in range(len - k):
                curr = curr.next
                
            head = curr.next
            curr.next = None
            
            return head

:::
* [把 linked list 加 1](https://leetcode.com/problems/plus-one-linked-list/)
給定一個表示非負整數的 linked list 的`head`，回傳表示該整數加上1的 linked list 的`head`。
:::spoiler 解答
這題和之前做過的[將兩個linked list相加](https://leetcode.com/problems/add-two-numbers/)類似，但是這題的linked list並沒有將數字反序儲存。因此，一個直覺的方法就是另外建立一個把原本的 list 反過來的 list，並進行簡單加法。然而，這麼做會消耗大量記憶體，在這邊我們可以使用不需要建立新 list 的方法。相對地，我們多次遍歷list，以時間換取空間。

    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    
    class Solution(object):
        def plusOne(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            start = None
            node = head
            
            while node:
                if node.val < 9:
                    start = node
                node = node.next

            if start:
                start.val += 1
                node = start.next
            else:
                new = ListNode(1)
                new.next = head
                node = head
                head = new

            while node:
                node.val = 0
                node = node.next

            return head

:::
* [相加兩個用 linked list 表示的多項式](https://leetcode.com/problems/add-two-polynomials-represented-as-linked-lists/)
多項式linked list是一種用來表示多項式的特殊 linked list 資料結構，其中每一個節點用來表示多項式的一個項。
每個節點有三個屬性：
* `coefficient`: 一個整數，表示該項的係數。例如，$9x^4$ 的`coefficient`就是 9。
* `power`: 一個整數，表示該項的次方數。例如，$9x^4$ 的`power`就是 4。
* `next`: 用來連結到下一項的參數。

舉例來說，$5x^3 + 4x - 7$ 用linked list的表示方式如下圖：
注意在這邊我們的多項式必須按照次方降冪排列，並且忽略掉係數為0的項。
現在，給定兩個多項式linked list的`head`：`poly1`和`poly2`，我們要回傳一個多項式的`head`，用來表示給定的兩個多項式相加的多項式。如果結果是0，回傳`None`。

:::spoiler 解答
這題事實上和merge兩個排列好的linked list類似。

    class Solution:
        def addPoly(self, poly1: 'PolyNode', poly2: 'PolyNode') -> 'PolyNode':
            head = node = PolyNode()
            while poly1 and poly2:
                if poly1.power > poly2.power:
                    node.next = node = poly1
                    poly1 = poly1.next
                elif poly1.power < poly2.power:
                    node.next = node = poly2
                    poly2 = poly2.next
                else:
                    if coef := poly1.coefficient+poly2.coefficient:
                        node.next = node = PolyNode(coef, poly1.power)
                    poly1, poly2 = poly1.next, poly2.next
            node.next = poly1 or poly2
            return head.next

:::