Algorithms 101: two linked lists

1. LeetCode 21: Merge Two Sorted Lists

Solution and Time Complexity Analysis:

# Python code
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode()
    current = dummy

    while l1 and l2:
        if l1.val < l2.val:  # If the value of l1 is less than l2
            current.next = l1  # Add the node of l1 to the new list
            l1 = l1.next  # Move to the next node in l1
        else:
            current.next = l2  # Add the node of l2 to the new list
            l2 = l2.next  # Move to the next node in l2
        current = current.next  # Move to the next position in the new list

    # If one of the lists still has nodes remaining, directly link them to the new list
    current.next = l1 if l1 else l2

    return dummy.next  # Return the merged list

Time and Space Complexity:

• Time Complexity: O(n + m), where n and m are the lengths of the two lists. We need to traverse all nodes in both lists.
• Space Complexity: O(1), as we are only using constant space to hold pointers.

2. LeetCode 23: Merge k Sorted Lists

Solution and Time Complexity Analysis:

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists: List[ListNode]) -> ListNode:
    dummy = ListNode()  # Create a dummy node
    current = dummy
    heap = []

    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))  # Push the head of each list into the heap

    while heap:
        val, i, node = heapq.heappop(heap)  # Pop the smallest node from the heap
        current.next = node  # Add the popped node to the result list
        current = current.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))  # Push the next node into the heap

    return dummy.next

Time and Space Complexity:

• Time Complexity: O(Nlogk), where N is the total number of nodes across all lists and k is the number of lists. Since we use a heap, each insertion or deletion in the heap takes O(logk).
• Space Complexity: O(k), for the space used by the heap, which holds the heads of up to k lists.

3. LeetCode 143: Reorder List

Solution and Time Complexity Analysis:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head: ListNode) -> None:
    if not head:
        return

    # Step 1: Find the middle of the linked list
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: Reverse the second half of the list
    prev, curr = None, slow.next
    slow.next = None
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp

    # Step 3: Merge the two halves
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

Time and Space Complexity:

• Time Complexity: O(n), where n is the length of the linked list. We traverse the list twice: once to find the middle and once to reverse the second half.
• Space Complexity: O(1), as we are only using constant space for pointers.

4. LeetCode 92: Reverse Linked List II

Solution and Time Complexity Analysis:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseBetween(head: ListNode, left: int, right: int) -> ListNode:
    if not head:
        return None

    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    # Step 1: Move to the node before 'left'
    for _ in range(left - 1):
        prev = prev.next

    # Step 2: Reverse the sublist between 'left' and 'right'
    curr = prev.next
    for _ in range(right - left):
        next_temp = curr.next
        curr.next = next_temp.next
        next_temp.next = prev.next
        prev.next = next_temp

    return dummy.next

Time and Space Complexity:

• Time Complexity: O(n), where n is the length of the list. We traverse the list once to find the positions ‘left’ and ‘right’, and then reverse the sublist.
• Space Complexity: O(1), as we only use constant space for pointers.

5. LeetCode 328: Odd Even Linked List

Solution and Time Complexity Analysis:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def oddEvenList(head: ListNode) -> ListNode:
    if not head:
        return None

    odd, even = head, head.next
    even_head = even

    while even and even.next:
        odd.next = even.next  # Connect odd nodes
        odd = odd.next
        even.next = odd.next  # Connect even nodes
        even = even.next

    odd.next = even_head  # Connect the even list after the odd list
    return head

Time and Space Complexity:

• Time Complexity: O(n), where n is the length of the list. We traverse the list once.
• Space Complexity: O(1), as we only use constant space for pointers.

Summary:

• These problems all involve manipulating nodes in linked lists, such as merging, reordering, and reversing nodes. The core idea is to efficiently manipulate the pointers in the list.
• Their time complexity is typically O(n), while space complexity can often be optimized to O(1) by only using pointer manipulation.

Let me know if you’d like more details on any of these problems!