Linked List

本記事は以下記事の一部です。

NeetCode 150 全問の解き方とポイントまとめ & 感想

Linked Listは最初とっつきにくくて考え方が独特に思える。特に競プロとかだとあまり見ないかも？TreeやGraphを理解するための前段階として教育的に知っておくと良いような感じ。実際Linked List自体は例えばJavaでも標準ライブラリに実装されてるし、よく使う。

最初、一旦全部配列に移し替えて、Arraysの問題として取り扱うようにすれば簡単じゃんと思ったし、実際それでSuccessする。が、Linked ListはLinked Listのまま取り扱うように理解することで知識の幅が広がるのと、Space Complexityも抑えることができるので、それで慣れておくと良い。

35. Reverse Linked List

Problem

Given the beginning of a singly linked list head, reverse the list, and return the new beginning of the list.

Example 1:

Input: head = [0,1,2,3]

Output: [3,2,1,0]

Copy

Example 2:

Input: head = []

Output: []

Copy

Constraints:

• 0 <= The length of the list <= 1000.
• -1000 <= Node.val <= 1000

Solution

# 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: Optional[ListNode]) -> Optional[ListNode]:
        curr = head
        prev = None
        while curr:
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp
        
        return prev

36. Merge Two Sorted Lists

Problem

Given the beginning of a singly linked list head, reverse the list, and return the new beginning of the list.

Example 1:

Input: head = [0,1,2,3]

Output: [3,2,1,0]

Copy

Example 2:

Input: head = []

Output: []

Copy

Constraints:

• 0 <= The length of the list <= 1000.
• -1000 <= Node.val <= 1000

Solution

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

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        curr = ListNode()
        dummy = curr

        while list1 and list2:
            if list1.val <= list2.val:
                # ここは dummy.next = ListNode(list1.val) でも良いが、
                # 以下の書き方でも問題なく、空間計算量を減らせる
                dummy.next = list1
                list1 = list1.next
            else:
                dummy.next = list2
                list2 = list2.next
            
            dummy = dummy.next
        
        # ↑まででどちらかは必ずなくなるが、片方余ってる可能性があるので、
        # そのままケツに繋げてあげる
        if list1:
            dummy.next = list1
        
        if list2:
            dummy.next = list2
        
        return curr.next

37. Reorder List

Problem

You are given the head of a singly linked-list.

The positions of a linked list of length = 7 for example, can intially be represented as:

[0, 1, 2, 3, 4, 5, 6]

Reorder the nodes of the linked list to be in the following order:

[0, 6, 1, 5, 2, 4, 3]

Notice that in the general case for a list of length = n the nodes are reordered to be in the following order:

[0, n-1, 1, n-2, 2, n-3, ...]

You may not modify the values in the list's nodes, but instead you must reorder the nodes themselves.

Example 1:

Input: head = [2,4,6,8]

Output: [2,8,4,6]

Copy

Example 2:

Input: head = [2,4,6,8,10]

Output: [2,10,4,8,6]

Copy

Constraints:

• 1 <= Length of the list <= 1000.
• 1 <= Node.val <= 1000

Solution

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

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        
        # 後半半分の先頭がslow.nextになる
        second = slow.next
        # 前半と後半を切り離す
        slow.next = None
        # 後半をひっくり返す
        prev = None
        while second:
            tmp = second.next
            second.next = prev
            prev = second
            second = tmp
        
        # prevに後半半分がひっくり返った先頭のポインタがあるので、
        # 再度secondに設定し直す
        second = prev

        # 前半半分は改めてheadを設定する
        first = head

        # secondがなくなるまでループを続ける
        # first -> second -> という感じで組み直す
        while second:
            tmp1 = first.next
            tmp2 = second.next
            first.next = second
            second.next = tmp1
            first = tmp1
            second = tmp2

38. Remove Nth Node From End of List

Problem

You are given the beginning of a linked list head, and an integer n.

Remove the nth node from the end of the list and return the beginning of the list.

Example 1:

Input: head = [1,2,3,4], n = 2

Output: [1,2,4]

Copy

Example 2:

Input: head = [5], n = 1

Output: []

Copy

Example 3:

Input: head = [1,2], n = 2

Output: [2]

Copy

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Solution

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

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = head
        slow = dummy
        fast = head

        # fastをn個だけ先に進めておく
        while n > 0:
            fast = fast.next
            n -= 1
        
        # fastが最後に辿り着くまでslowも一緒に進める
        while fast:
            slow = slow.next
            fast = fast.next
        
        # slowが後ろからn番目の値の一つ前に来ているので、
        # n番目を飛ばす
        slow.next = slow.next.next

        # 改めてheadを返す
        return dummy.next

39. Copy List With Random Pointer

Problem

You are given the head of a linked list of length n. Unlike a singly linked list, each node contains an additional pointer random, which may point to any node in the list, or null.

Create a deep copy of the list.

The deep copy should consist of exactly n new nodes, each including:

• The original value val of the copied node
• A next pointer to the new node corresponding to the next pointer of the original node
• A random pointer to the new node corresponding to the random pointer of the original node

Note: None of the pointers in the new list should point to nodes in the original list.

Return the head of the copied linked list.

In the examples, the linked list is represented as a list of n nodes. Each node is represented as a pair of [val, random_index] where random_index is the index of the node (0-indexed) that the random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[3,null],[7,3],[4,0],[5,1]]

Output: [[3,null],[7,3],[4,0],[5,1]]

Copy

Example 2:

Input: head = [[1,null],[2,2],[3,2]]

Output: [[1,null],[2,2],[3,2]]

Copy

Constraints:

• 0 <= n <= 100
• -100 <= Node.val <= 100
• random is null or is pointing to some node in the linked list.

Solution

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        old_copy_map = { None: None }

        curr = head
        while curr:
            copy = Node(curr.val)
            old_copy_map[curr] = copy
            curr = curr.next
        
        curr = head
        while curr:
            copy = old_copy_map[curr]
            copy.next = old_copy_map[curr.next]
            copy.random = old_copy_map[curr.random]
            curr = curr.next
        
        return old_copy_map[head]

40. Add Two Numbers

Problem

You are given the head of a linked list of length n. Unlike a singly linked list, each node contains an additional pointer random, which may point to any node in the list, or null.

Create a deep copy of the list.

The deep copy should consist of exactly n new nodes, each including:

• The original value val of the copied node
• A next pointer to the new node corresponding to the next pointer of the original node
• A random pointer to the new node corresponding to the random pointer of the original node

Note: None of the pointers in the new list should point to nodes in the original list.

Return the head of the copied linked list.

In the examples, the linked list is represented as a list of n nodes. Each node is represented as a pair of [val, random_index] where random_index is the index of the node (0-indexed) that the random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[3,null],[7,3],[4,0],[5,1]]

Output: [[3,null],[7,3],[4,0],[5,1]]

Copy

Example 2:

Input: head = [[1,null],[2,2],[3,2]]

Output: [[1,null],[2,2],[3,2]]

Copy

Constraints:

• 0 <= n <= 100
• -100 <= Node.val <= 100
• random is null or is pointing to some node in the linked list.

Solution

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

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        ans = ListNode()
        dummy = ans
        carry = 0

        while l1 or l2 or carry:
            total = carry
            if l1:
                total += l1.val
                l1 = l1.next
            
            if l2:
                total += l2.val
                l2 = l2.next
            
            dummy.next = ListNode(total % 10)
            # totalが10を超えてたら1を次に引き継ぐ
            carry = total // 10
            
            dummy = dummy.next
        
        return ans.next

41. Linked List Cycle

Problem

Given the beginning of a linked list head, return true if there is a cycle in the linked list. Otherwise, return false.

There is a cycle in a linked list if at least one node in the list that can be visited again by following the next pointer.

Internally, index determines the index of the beginning of the cycle, if it exists. The tail node of the list will set it's next pointer to the index-th node. If index = -1, then the tail node points to null and no cycle exists.

Note: index is not given to you as a parameter.

Example 1:

Input: head = [1,2,3,4], index = 1

Output: true

Copy

Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], index = -1

Output: false

Copy

Constraints:

• 1 <= Length of the list <= 1000.
• -1000 <= Node.val <= 1000
• index is -1 or a valid index in the linked list.

Solution

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

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True
        
        return False

42. Find The Duplicate Number

Problem

Given the beginning of a linked list head, return true if there is a cycle in the linked list. Otherwise, return false.

There is a cycle in a linked list if at least one node in the list that can be visited again by following the next pointer.

Internally, index determines the index of the beginning of the cycle, if it exists. The tail node of the list will set it's next pointer to the index-th node. If index = -1, then the tail node points to null and no cycle exists.

Note: index is not given to you as a parameter.

Example 1:

Input: head = [1,2,3,4], index = 1

Output: true

Copy

Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], index = -1

Output: false

Copy

Constraints:

• 1 <= Length of the list <= 1000.
• -1000 <= Node.val <= 1000
• index is -1 or a valid index in the linked list.

Solution

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = 0, 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]

            if slow == fast:
                break
        
        slow2 = 0
        while True:
            slow = nums[slow]
            slow2 = nums[slow2]

            if slow == slow2:
                return slow2

43. LRU Cache

Problem

Implement the Least Recently Used (LRU) cache class LRUCache. The class should support the following operations

• LRUCache(int capacity) Initialize the LRU cache of size capacity.
• int get(int key) Return the value cooresponding to the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the introduction of the new pair causes the cache to exceed its capacity, remove the least recently used key.

A key is considered used if a get or a put operation is called on it.

Ensure that get and put each run in O(1)O(1) average time complexity.

Example 1:

Input:
["LRUCache", [2], "put", [1, 10],  "get", [1], "put", [2, 20], "put", [3, 30], "get", [2], "get", [1]]

Output:
[null, null, 10, null, null, 20, -1]

Explanation:
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 10);  // cache: {1=10}
lRUCache.get(1);      // return 10
lRUCache.put(2, 20);  // cache: {1=10, 2=20}
lRUCache.put(3, 30);  // cache: {2=20, 3=30}, key=1 was evicted
lRUCache.get(2);      // returns 20 
lRUCache.get(1);      // return -1 (not found)

Copy

Constraints:

• 1 <= capacity <= 100
• 0 <= key <= 1000
• 0 <= value <= 1000

Solution

class ListNode:
    def __init__(self, key: int, val: int):
        self.key = key
        self.val = val
        self.prev = None
        self.nxt = None

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {} # key -> node
        self.left = ListNode(0, 0)
        self.right = ListNode(0, 0)
        self.left.nxt = self.right
        self.right.prev = self.left

    def add(self, node: ListNode) -> None:
        prev, nxt = self.right.prev, self.right
        prev.nxt = node
        nxt.prev = node
        node.nxt = self.right
        node.prev = prev
    
    def remove(self, node: ListNode) -> None:
        prev, nxt = node.prev, node.nxt
        prev.nxt = nxt
        nxt.prev = prev

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        
        # remove→addすることで、cacheが使われた状態を更新する
        node = self.cache[key]
        self.remove(node)
        self.add(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # keyが存在する場合は元のkeyに紐づいたnodeをまず削除
            target_node = self.cache[key]
            self.remove(target_node)
        
        # nodeを新しく作成して追加
        new_node = ListNode(key, value)
        self.cache[key] = new_node
        self.add(new_node)
        
        if len(self.cache) > self.capacity:
            lru = self.left.nxt
            self.remove(lru)
            del self.cache[lru.key]

44. Merge K Sorted Linked Lists

Problem

Implement the Least Recently Used (LRU) cache class LRUCache. The class should support the following operations

• LRUCache(int capacity) Initialize the LRU cache of size capacity.
• int get(int key) Return the value cooresponding to the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the introduction of the new pair causes the cache to exceed its capacity, remove the least recently used key.

A key is considered used if a get or a put operation is called on it.

Ensure that get and put each run in O(1)O(1) average time complexity.

Example 1:

Input:
["LRUCache", [2], "put", [1, 10],  "get", [1], "put", [2, 20], "put", [3, 30], "get", [2], "get", [1]]

Output:
[null, null, 10, null, null, 20, -1]

Explanation:
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 10);  // cache: {1=10}
lRUCache.get(1);      // return 10
lRUCache.put(2, 20);  // cache: {1=10, 2=20}
lRUCache.put(3, 30);  // cache: {2=20, 3=30}, key=1 was evicted
lRUCache.get(2);      // returns 20 
lRUCache.get(1);      // return -1 (not found)

Copy

Constraints:

• 1 <= capacity <= 100
• 0 <= key <= 1000
• 0 <= value <= 1000

Solution

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

class Solution:    
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None

        while len(lists) > 1:
            merged_list = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i+1] if (i+1) < len(lists) else None
                merged = self.merge(l1, l2)
                merged_list.append(merged)
            lists = merged_list
        
        return lists[0]

    def merge(self, l1: ListNode, l2: ListNode) -> ListNode:
        ans = ListNode()
        dummy = ans
        while l1 and l2:
            if l1.val <= l2.val:
                dummy.next = l1
                l1 = l1.next
            else:
                dummy.next = l2
                l2 = l2.next
            dummy = dummy.next
        
        if l1:
            dummy.next = l1
        
        if l2:
            dummy.next = l2
        
        return ans.next

45. Reverse Nodes In K Group

Problem

You are given the head of a singly linked list head and a positive integer k.

You must reverse the first k nodes in the linked list, and then reverse the next k nodes, and so on. If there are fewer than k nodes left, leave the nodes as they are.

Return the modified list after reversing the nodes in each group of k.

You are only allowed to modify the nodes' next pointers, not the values of the nodes.

Example 1:

Input: head = [1,2,3,4,5,6], k = 3

Output: [3,2,1,6,5,4]

Copy

Example 2:

Input: head = [1,2,3,4,5], k = 3

Output: [3,2,1,4,5]

Copy

Constraints:

• The length of the linked list is n.
• 1 <= k <= n <= 100
• 0 <= Node.val <= 100

Solution

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

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = head
        groupPrev = dummy

        while True:
            kthNode = self.findKthNode(groupPrev, k)
            if not kthNode:
                break

            nextGroupFirst = kthNode.next

            # 反転した後の先頭は次のグループの先頭
            # (単に反転する際はprev=Noneだった)
            prev = kthNode.next
            curr = groupPrev.next
            while curr != nextGroupFirst:
                tmp = curr.next
                curr.next = prev
                prev = curr
                curr = tmp
            
            tmp = groupPrev.next # 1をtmpに
            groupPrev.next = kthNode # 0→3に繋げる
            groupPrev = tmp # 1をgroupPrevに

        return dummy.next
    

    def findKthNode(self, node: ListNode, k: int) -> ListNode:
        while node and k > 0:
            k -= 1
            node = node.next
        
        return node