Swapping Nodes in a Linked List

Medium

Swapping Nodes in a Linked List

Medium

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:

What is the range of values for the nodes in the linked list, and can k ever be larger than the number of nodes in the linked list?
Can the linked list be empty (i.e., head is null), and if so, what should I return?
Is `k` guaranteed to be a valid positive integer (i.e., k > 0)?
Are the node values unique, or can there be duplicate values in the linked list?
Should I return the modified linked list by changing the `next` pointers of the existing nodes, or is creating a completely new linked list acceptable?

Brute Force Solution

Approach

The brute force method for swapping nodes in a linked list involves checking every single possible pair of nodes to swap and evaluating the resulting list. It's like trying every combination until you find the right one. This ensures we explore every possibility, but it might take a while.

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

Consider the first node in the linked list.
Try swapping the first node with the second node and see what happens to the list.
Then, swap the first node with the third node and see what happens to the list.
Keep swapping the first node with every other node in the list, one at a time, and observe the outcome.
Now, move to the second node and repeat the process.
Try swapping the second node with every node that comes after it in the list.
Continue this process for each node in the list, making sure you don't repeat any swaps.
After trying all possible swaps, identify the specific swap or swaps that result in the desired list configuration, if any.

Code Implementation

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

def brute_force_swap_nodes(head):
    current_node = head
    while current_node:
        next_node = current_node.next
        while next_node:
            # Attempt to swap the values of the current node with the next node
            current_node.val, next_node.val = next_node.val, current_node.val

            # Move to the next node for further potential swaps
            next_node = next_node.next
        current_node = current_node.next

    return head

Big(O) Analysis

Time Complexity

O(n²) – The provided approach attempts to swap each node in the linked list with every other node. For a linked list of size n, the outer loop iterates through each of the n nodes. The inner loop, for each node, iterates through roughly the remaining n nodes to attempt a swap. This leads to a nested loop structure where approximately n * (n-1) / 2 swap operations are considered. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The brute force method described only involves swapping nodes in place. No auxiliary data structures like arrays, hash maps, or additional linked lists are created to store intermediate results or track visited nodes. The algorithm solely uses a few pointer variables to traverse and swap nodes within the original linked list. Therefore, the space used remains constant irrespective of the number of nodes, N, in the linked list.

Optimal Solution

Approach

To swap two nodes in a linked list efficiently, focus on adjusting the connections of the nodes around the ones you want to swap. This avoids unnecessary changes to the rest of the list and lets you swap the nodes by modifying only a few connections.

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

First, find the two nodes you want to swap and also identify the nodes that come right before them. We'll call these 'previous' nodes.
Next, carefully change the connection of the 'previous' node of the first node to point to the second node. This disconnects the first node from its old spot.
Then, adjust the connection of the 'previous' node of the second node to point to the first node. This detaches the second node from its old spot.
Now, point the first node to whatever the second node was originally pointing to. This links the first node into its new location.
Finally, point the second node to whatever the first node was originally pointing to. This links the second node into its new location.
If either of the nodes you want to swap is the very first node in the list, you'll also need to update the list's starting point to be the other node after the swap.
By carefully adjusting these connections, you've effectively swapped the two nodes without needing to copy any data or move large portions of the list.

Code Implementation

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

def swap_nodes(head, first_node_value, second_node_value):
    if first_node_value == second_node_value:
        return head

    previous_node_first_node = None
    current_node_first_node = head
    while current_node_first_node and current_node_first_node.val != first_node_value:
        previous_node_first_node = current_node_first_node
        current_node_first_node = current_node_first_node.next

    previous_node_second_node = None
    current_node_second_node = head
    while current_node_second_node and current_node_second_node.val != second_node_value:
        previous_node_second_node = current_node_second_node
        current_node_second_node = current_node_second_node.next

    # If either node is not found, return the original list.
    if not current_node_first_node or not current_node_second_node:
        return head

    # Update the 'previous' pointer of the first node. 
    if previous_node_first_node:
        previous_node_first_node.next = current_node_second_node
    else:
        # If the first node is the head, update the head.
        head = current_node_second_node

    # Update the 'previous' pointer of the second node.
    if previous_node_second_node:
        previous_node_second_node.next = current_node_first_node
    else:
        # If the second node is the head, update the head.
        head = current_node_first_node

    # Swap the next pointers of the two nodes.
    temporary_node = current_node_first_node.next
    current_node_first_node.next = current_node_second_node.next
    current_node_second_node.next = temporary_node

    return head

Big(O) Analysis

Time Complexity

O(n) – The algorithm involves finding two nodes within the linked list, which in the worst case, requires traversing the entire list once for each node to be swapped. Specifically, locating the two nodes to swap and their preceding nodes requires at most one pass through the linked list of size n. Adjusting the pointers of the involved nodes then takes constant time. Therefore, the time complexity is dominated by the search, resulting in O(n).

Space Complexity

O(1) – The algorithm identifies the nodes to be swapped and their preceding nodes using a few pointer variables. Regardless of the linked list size (N), the number of pointers used to track nodes remains constant. No additional data structures like arrays or hash maps are created, and the recursion depth is not dependent on the size of the linked list. Therefore, the auxiliary space complexity is O(1), indicating constant space usage.

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 head as is since no swapping is needed.
List with two nodes and k=1	Swap the first and last (which are the only two) nodes and return the head.
k is greater than the list length	Do nothing, or return an error; the swap should not modify the list and the original list should be returned.
k is equal to the list length	Swap the first and last nodes and return the head.
k is 1	Swap the first and last node in the list.
k is in the middle of the list, but the kth node from the beginning and the kth node from the end are the same node	No swap is needed; return the head as is.
Large list to verify performance and potential memory issues if using auxiliary data structures	The iterative solution should scale efficiently without causing memory issues.