[Leetcode] LinkedList

Reverse & Sorting Problem

25. Reverse Nodes in K-Group

Leetcode: https://leetcode.com/problems/reverse-nodes-in-k-group/description/

[Solution]

1. Find k + 1th node
2. Use a stack to reverse k nodes
3. Link the reversed part with k + 1th node
4. Recursively do above till head is null

def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
    if not head:
        return None
    cur = head
    cnt = 0
    stack = []
    while cur and len(stack) < k:
        stack.append(cur)
        cur = cur.next
    if len(stack) < k:
        return head
    newhead = stack.pop()
    res = newhead
    while stack:
        newhead.next = stack.pop()
        newhead = newhead.next
    
    newhead.next = self.reverseKGroup(cur, k)
    return res

92. Reverse Linked List II

Leetcode: https://leetcode.com/problems/reverse-linked-list-ii/

Note: Beware of cases when m = 1

def reverseBetween(self, head, m, n):
    """
    :type head: ListNode
    :type m: int
    :type n: int
    :rtype: ListNode
    """
    cur = head
    prev = None
    for i in range(m - 1):
        prev = cur
        cur = cur.next
    tail = cur
    r = None
    for i in range(n - m + 1):
        n = cur.next
        cur.next = r
        r = cur
        cur = n
    tail.next = n
    if prev:
        prev.next = r
    if m == 1:
        return r
    return head

24. Swap Nodes in Pairs

Leetcode: https://leetcode.com/problems/swap-nodes-in-pairs/

def swapPairs(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    cur = head
    res = ListNode(0)
    dummy = res
    while cur:
        _next = cur.next
        if not _next:
            dummy.next = cur
            break
        unsorted = _next.next
        _next.next, cur.next = cur, None
        dummy.next = _next
        dummy = cur
        cur = unsorted
    return res.next

138. Copy List with Random Pointer

Leetcode: https://leetcode.com/problems/copy-list-with-random-pointer/solution/

[Solution]:

1. Use a dict to track visited nodes
2. If current node is in the visited dict, use visited[node], else return a new copy of node

class Solution(object):
    def __init__(self):
        self.visited = {}
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return
        if head in self.visited:
            return self.visited[head]
        
        node = Node(head.val, None, None)
        self.visited[head] = node
        node.next = self.copyRandomList(head.next)
        node.random = self.copyRandomList(head.random)
        return node

[Similar Problems]

1. Clone Graph

86. Partition List

Leetcode: https://leetcode.com/problems/partition-list/

Note: Remember to set large.next = None after the iteration. Or there might be cycle in the returned linked list!

def partition(self, head: ListNode, x: int) -> ListNode:
    small_head, large_head = ListNode(0), ListNode(0)
    small, large = small_head, large_head
    cur = head
    while cur:
        if cur.val < x:
            small.next = cur
            small = small.next
        if cur.val >= x:
            large.next = cur
            large = large.next
        cur = cur.next
    large.next = None # !!!
    small.next = large_head.next
    return small_head.next

Stack with ordering

1019. Next Greater Node In Linked List

Leetcode: https://leetcode.com/problems/next-greater-node-in-linked-list/

Note:

1. Use a stack, keep the stack with descending order

def nextLargerNodes(self, head):
    stack = [] # [[0,2]]
    index = 0
    d = collections.defaultdict(int)
    while head:
        while stack and stack[-1][1] < head.val:
            v = stack.pop()
            d[v[0]] = head.val
        stack.append([index, head.val])
        index += 1
        head = head.next
    res = [0] * index
    for i in range(len(res)):
        res[i] = d[i]
    return res