How do you solve Swapping Nodes in a Linked List on LeetCode?

Swapping Nodes in a Linked List (LeetCode #1721) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Using two pointers allows us to find nodes efficiently.

What is the brute force solution for Swapping Nodes in a Linked List?

The brute force approach for Swapping Nodes in a Linked List is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach involves converting the linked list into an array, allowing us to easily access and swap the required nodes using their indices. This method is straightforward but not the most efficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Swapping Nodes in a Linked List?

Swapping Nodes in a Linked List uses the following concepts: Linked List, Two Pointers. The recommended patterns to study are: Two Pointers, Linked List.

What are the interview tips for Swapping Nodes in a Linked List?

Clarify the input constraints and edge cases. Explain your thought process while coding. Consider both time and space complexity in your solution.

What are common mistakes when solving Swapping Nodes in a Linked List?

Not handling edge cases like k being 1 or equal to the length of the list. Confusing 1-indexing with 0-indexing.

#1721

Swapping Nodes in a Linked List

Medium

Linked ListTwo PointersTwo PointersLinked List

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach uses two pointers to find the k-th node from the beginning and the k-th node from the end in a single pass through the linked list. This is more efficient as it avoids the need for extra space and multiple traversals.

⚙️

Algorithm

5 steps

1Step 1: Initialize two pointers, 'first' and 'second', both starting at the head.
2Step 2: Move 'first' k-1 steps forward to reach the k-th node from the beginning.
3Step 3: Move 'second' pointer to the head and move both 'first' and 'second' pointers until 'first' reaches the end of the list. This will position 'second' at the k-th node from the end.
4Step 4: Swap the values of the nodes pointed by 'first' and 'second'.
5Step 5: Return the head of the modified linked list.

solution.py17 lines

1# Full working Python code
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7def swapNodes(head, k):
8    first = head
9    second = head
10    for _ in range(k - 1):
11        first = first.next
12    temp = first
13    while temp.next:
14        temp = temp.next
15        second = second.next
16    first.val, second.val = second.val, first.val
17    return head

ℹ

Complexity note: The time complexity is O(n) because we traverse the linked list only once to find the k-th nodes. The space complexity is O(1) since we are not using any additional data structures that grow with input size.

1Using two pointers allows us to find nodes efficiently.
2Swapping values is simpler than swapping nodes in a linked list.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.