#1721

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Swapping Nodes in a Linked List

Swap nodes in a linked list using linked-list pointer manipulation and two pointers to solve this medium difficulty problem.

linked list two pointers

Problem Statement

You are given the head of a linked list and an integer k. Your task is to return the head of the linked list after swapping the kth node from the beginning with the kth node from the end. The list is 1-indexed, meaning that the first node is numbered 1.

The problem challenges you to manipulate the pointers of the linked list effectively. A direct approach would involve traversing the entire list to locate the nodes and swap their values, but an optimized solution requires careful management of pointers without excessive space usage.

Examples

Example 1

Input: head = [1,2,3,4,5], k = 2

Output: [1,4,3,2,5]

Example details omitted.

Example 2

Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5

Output: [7,9,6,6,8,7,3,0,9,5]

Example details omitted.

Constraints

The number of nodes in the list is n.
1 <= k <= n <= 105
0 <= Node.val <= 100

Solution Approach

Pointer Traversal with Two Pointers

Utilize a two-pointer technique to find the kth node from both the beginning and the end. First, move one pointer to the kth node from the start, then traverse with the second pointer to the end of the list while keeping track of the kth node from the end. This reduces time complexity and ensures that the swap happens in one pass through the list.

Storing Node Values in an Array

An alternate approach is to traverse the list once, storing all the node values in an array. Once the array is populated, you can directly swap the values of the kth node from the beginning and the kth node from the end. This approach is simpler but requires additional space.

Optimized In-Place Swapping

For an optimal solution, perform the swapping without extra space by locating both the kth nodes during a single traversal. This approach modifies pointers in-place, minimizing space complexity while maintaining linear time complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the method used. With two pointers, the solution runs in O(n) time, where n is the number of nodes in the list. Storing nodes in an array also requires O(n) time but uses additional space O(n). The in-place approach has O(n) time complexity and O(1) space complexity due to pointer manipulation.

What Interviewers Usually Probe

Candidate should consider both time and space complexity when discussing their approach.
Look for an understanding of two-pointer techniques and linked-list manipulation.
Candidates should be able to explain how they can optimize the problem by avoiding unnecessary space usage.

Common Pitfalls or Variants

Common pitfalls

Failing to handle edge cases such as when k is exactly at the middle of the list or when the list has only one node.
Using extra space unnecessarily when an in-place solution is possible.
Not correctly identifying the kth node from the end by failing to account for list length or pointer alignment.

Follow-up variants

What if the linked list is circular? How would the approach change?
Modify the problem to swap multiple nodes, not just the kth node from the start and end.
Optimize the problem to work with doubly linked lists.

FAQ

How do you solve the 'Swapping Nodes in a Linked List' problem optimally?

To solve this optimally, use two pointers to find the kth node from both the start and the end. Swap their values in-place, avoiding extra space usage.

What is the time complexity of the 'Swapping Nodes in a Linked List' problem?

The time complexity is O(n) because you traverse the linked list once to find the kth node from both ends.

How can the 'Swapping Nodes in a Linked List' problem be solved using an array?

By traversing the list once and storing node values in an array, you can swap the kth node from the beginning and the kth node from the end using direct indexing.

What are some common mistakes in the 'Swapping Nodes in a Linked List' problem?

Common mistakes include not handling edge cases like k being in the middle, using unnecessary space, or failing to correctly swap nodes using pointer manipulation.

What pattern is important in the 'Swapping Nodes in a Linked List' problem?

The primary pattern is linked-list pointer manipulation, and the two-pointer technique can be used to optimize the solution.

terminal

Solution

Solution 1: Two Pointers

We can first use a fast pointer `fast` to find the $k$th node of the linked list, and use a pointer `p` to point to it. Then, we use a slow pointer `slow` to start from the head node of the linked list, and move both pointers forward at the same time. When the fast pointer reaches the last node of the linked list, the slow pointer `slow` points to the $k$th node from the end of the linked list, and we use a pointer `q` to point to it. At this point, we only need to swap the values of `p` and `q`.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        fast = slow = head
        for _ in range(k - 1):
            fast = fast.next
        p = fast
        while fast.next:
            fast, slow = fast.next, slow.next
        q = slow
        p.val, q.val = q.val, p.val
        return head

Continue Practicing

#2095 delete the middle node of a linked list #2130 maximum twin sum of a linked list #876 middle of the linked list