Jobs

Interviews

Discussions

Swap Nodes in Pairs

Medium

Google

1 view

Topics:

Linked Lists

You are given the head of a singly linked list. You need to swap every two adjacent nodes and return the new head of the linked list. The critical requirement is that you must solve the problem without modifying the values in the list's nodes. In other words, only the nodes themselves can be changed.

For instance:

If the input linked list is 1 -> 2 -> 3 -> 4, the output should be 2 -> 1 -> 4 -> 3.
If the input is an empty list, i.e., [], the output should also be [].
If the input list has only one node, e.g., [1], the output should remain [1].
If the input is 1 -> 2 -> 3, the output should be 2 -> 1 -> 3.

Explain your approach, analyze its time and space complexity, and handle any relevant edge cases. Provide code that implements the solution.

Swap Nodes in Pairs

Medium

Google

1 view

Topics:

Linked Lists

For instance:

If the input linked list is 1 -> 2 -> 3 -> 4, the output should be 2 -> 1 -> 4 -> 3.
If the input is an empty list, i.e., [], the output should also be [].
If the input list has only one node, e.g., [1], the output should remain [1].
If the input is 1 -> 2 -> 3, the output should be 2 -> 1 -> 3.

Explain your approach, analyze its time and space complexity, and handle any relevant edge cases. Provide code that implements the solution.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list be empty, or contain only one node?
What is the data type of the values stored in the linked list nodes, and are there any constraints on the range of these values?
Is the 'head' argument guaranteed to be a valid pointer to the beginning of the linked list, or could it be null?
Should I modify the original linked list or create a new one? (I understand the prompt says 'only nodes themselves may be changed' but confirming the intent)
If the list has an odd number of nodes, what should happen to the last node? Should it remain in its original position?

Brute Force Solution

Approach

The brute force approach tackles this problem by looking at the list of items two at a time, and for each pair, swapping them if needed. We proceed down the list, addressing each pair sequentially. This process guarantees that the result is the correct pairwise swapping.

Here's how the algorithm would work step-by-step:

Look at the first two items in the list.
Swap the positions of these two items.
Move on to the next two items in the list. (The third and fourth items).
Swap the positions of these two items.
Continue this process of looking at two items and swapping them until you reach the end of the list.
If the list has an odd number of items, the last item will be left alone, since it doesn't have a pair to swap with.

Code Implementation

def swap_nodes_in_pairs(head):
    # Handle the base case of an empty list.
    if not head or not head.next:
        return head

    current_node = head

    # Iterate through the list, swapping pairs of nodes.
    while current_node and current_node.next:
        # Store the next node to facilitate the swap.
        next_node = current_node.next

        # Swap the values of the current and next nodes.
        current_node.val, next_node.val = next_node.val, current_node.val

        # Move to the next pair of nodes.
        current_node = next_node.next

    return head

Big(O) Analysis

Time Complexity

O(n) – The provided approach iterates through the linked list, examining pairs of nodes sequentially. For a list of n nodes, it processes approximately n/2 pairs. Each pair requires a constant number of operations (swapping pointers). Therefore, the total number of operations is proportional to n/2, which simplifies to O(n).

Space Complexity

O(1) – The described brute force approach operates directly on the input list, swapping nodes in place. It does not require any additional data structures like auxiliary arrays or hash maps to store intermediate results or visited nodes. The space used is therefore constant, independent of the number of nodes, N, in the list. This means the algorithm's space complexity is O(1).

Optimal Solution

Approach

The goal is to rearrange a linked list by swapping adjacent pairs. We can achieve this efficiently by updating connections directly, rather than moving the actual data. This avoids unnecessary operations and leads to a faster solution.

Here's how the algorithm would work step-by-step:

Imagine you have a chain of linked elements. Focus on grabbing two elements at a time.
Rearrange the chain so that the second element of the pair now points to the first.
Make sure the first element of the pair points to what the second element used to point to, effectively continuing the chain.
Before rearranging the chain, remember the element that came *before* the current pair; this is important to maintain the integrity of the larger chain.
After rearranging the current pair, link the element before the pair, to the second element, linking it into the rearranged chain.
Move along the chain in pairs, repeating the rearrangement. Keep going until you reach the end of the chain or the last element doesn't have a partner.
The beginning of the list might change. Keep track of where the re-arranged list starts and return that.

Code Implementation

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

def swapPairs(head):
    dummy_node = ListNode(0)
    dummy_node.next = head
    previous_node = dummy_node

    while head and head.next:
        # Nodes to be swapped
        first_node = head
        second_node = head.next

        # Correct the 'previous' pointer
        previous_node.next = second_node

        # Swapping
        first_node.next = second_node.next
        second_node.next = first_node

        # Move to the next pair
        # Necessary to relink list
        previous_node = first_node

        head = first_node.next

    return dummy_node.next

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list, processing two nodes at a time. Each node in the list is visited and rearranged exactly once. Therefore, the number of operations is directly proportional to the number of nodes (n) in the linked list. This single pass through the list results in a time complexity of O(n).

Space Complexity

O(1) – The algorithm operates directly on the linked list by re-wiring pointers. It utilizes a few pointer variables (such as 'previous', 'current', and 'next') to keep track of nodes during the swapping process, but the number of these variables remains constant regardless of the length (N) of the linked list. No auxiliary data structures like arrays or hash maps are created. Therefore, the extra space used is constant and independent of the input size N.

Edge Cases

Case	How to Handle
Empty list (head is null)	Return null immediately, as there are no nodes to swap.
List with only one node	Return the original head, as there's nothing to swap.
List with an even number of nodes	The algorithm should correctly swap all pairs until the end.
List with an odd number of nodes	The last node should remain unchanged after swapping the previous pairs.
Very long list (potential stack overflow with recursion)	Use an iterative approach to avoid stack overflow issues with large lists.
List containing nodes with duplicate values.	The solution should correctly swap nodes regardless of their values, focusing solely on node rearrangement, not value uniqueness.
Memory limitations when dealing with extremely large lists	Iterative approach preferable as it typically uses a constant amount of extra memory.
Null pointer exception during swapping	Carefully manage pointers to prevent null pointer exceptions during each swap operation.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list be empty, or contain only one node?
What is the data type of the values stored in the linked list nodes, and are there any constraints on the range of these values?
Is the 'head' argument guaranteed to be a valid pointer to the beginning of the linked list, or could it be null?
Should I modify the original linked list or create a new one? (I understand the prompt says 'only nodes themselves may be changed' but confirming the intent)
If the list has an odd number of nodes, what should happen to the last node? Should it remain in its original position?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Look at the first two items in the list.
Swap the positions of these two items.
Move on to the next two items in the list. (The third and fourth items).
Swap the positions of these two items.
Continue this process of looking at two items and swapping them until you reach the end of the list.
If the list has an odd number of items, the last item will be left alone, since it doesn't have a pair to swap with.

Code Implementation

def swap_nodes_in_pairs(head):
    # Handle the base case of an empty list.
    if not head or not head.next:
        return head

    current_node = head

    # Iterate through the list, swapping pairs of nodes.
    while current_node and current_node.next:
        # Store the next node to facilitate the swap.
        next_node = current_node.next

        # Swap the values of the current and next nodes.
        current_node.val, next_node.val = next_node.val, current_node.val

        # Move to the next pair of nodes.
        current_node = next_node.next

    return head

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have a chain of linked elements. Focus on grabbing two elements at a time.
Rearrange the chain so that the second element of the pair now points to the first.
Make sure the first element of the pair points to what the second element used to point to, effectively continuing the chain.
Before rearranging the chain, remember the element that came *before* the current pair; this is important to maintain the integrity of the larger chain.
After rearranging the current pair, link the element before the pair, to the second element, linking it into the rearranged chain.
Move along the chain in pairs, repeating the rearrangement. Keep going until you reach the end of the chain or the last element doesn't have a partner.
The beginning of the list might change. Keep track of where the re-arranged list starts and return that.

Code Implementation

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

def swapPairs(head):
    dummy_node = ListNode(0)
    dummy_node.next = head
    previous_node = dummy_node

    while head and head.next:
        # Nodes to be swapped
        first_node = head
        second_node = head.next

        # Correct the 'previous' pointer
        previous_node.next = second_node

        # Swapping
        first_node.next = second_node.next
        second_node.next = first_node

        # Move to the next pair
        # Necessary to relink list
        previous_node = first_node

        head = first_node.next

    return dummy_node.next

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty list (head is null)	Return null immediately, as there are no nodes to swap.
List with only one node	Return the original head, as there's nothing to swap.
List with an even number of nodes	The algorithm should correctly swap all pairs until the end.
List with an odd number of nodes	The last node should remain unchanged after swapping the previous pairs.
Very long list (potential stack overflow with recursion)	Use an iterative approach to avoid stack overflow issues with large lists.
List containing nodes with duplicate values.	The solution should correctly swap nodes regardless of their values, focusing solely on node rearrangement, not value uniqueness.
Memory limitations when dealing with extremely large lists	Iterative approach preferable as it typically uses a constant amount of extra memory.
Null pointer exception during swapping	Carefully manage pointers to prevent null pointer exceptions during each swap operation.