Is Swapping Nodes in a Linked List easy or hard?

This problem is typically classified as Medium difficulty. The challenge comes from correctly locating the kth node from the end without extra memory. Understanding linked list traversal and the two-pointer technique makes the solution straightforward.

Swapping Nodes in a Linked List Python/Java solution

Most implementations keep two node references and swap their values. The logic is identical across languages like Python, Java, C++, and JavaScript: traverse to the kth node, locate the kth node from the end using two pointers, then exchange their values in O(1) space.

How to solve Swapping Nodes in a Linked List in O(n)?

Traverse the list until the kth node from the start is reached and store that reference. Continue traversing while moving another pointer from the head at the same time. When the traversal pointer reaches the last node, the second pointer will point to the kth node from the end. Swap the node values to finish the operation in O(n) time.

What is the best approach for Swapping Nodes in a Linked List?

The single-pass two pointers approach is the most efficient and commonly expected solution. You locate the kth node from the start, then move another pointer from the head while continuing the traversal. When the first pointer reaches the end, the second pointer lands on the kth node from the end. This method runs in O(n) time with O(1) extra space.

Is Swapping Nodes in a Linked List asked at Google/Amazon/Meta?

Linked list pointer manipulation problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variations often test two-pointer techniques, node traversal, and edge cases involving head or tail nodes.

What data structure is used in Swapping Nodes in a Linked List?

The problem operates on a singly linked list. The main techniques involve pointer traversal and the two-pointer pattern to locate nodes efficiently without converting the list into another data structure.

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

Both common approaches run in O(n) time where n is the number of nodes in the list. The two-pass solution performs two linear traversals, while the optimized two-pointer method completes the task in a single traversal. Each approach uses O(1) extra space since only a few pointer variables are required.

Description Hints 3 Solution Video 5:31

1721. Swapping Nodes in a Linked List

Medium69.9% acceptance6 companies

You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the k^th node from the beginning and the k^th node from the end (the list is 1-indexed).

Example 1:

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

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]

Constraints:

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

Asked at 6 companies

Amazon

Google Oracle Microsoft Meta Bloomberg

Topics

Linked List Two Pointers

Hints open one at a time

Hint 1

We can traverse the linked list and store the elements in an array.

Hint 2

Upon conversion to an array, we can swap the required elements by indexing the array.

Hint 3

We can rebuild the linked list using the order of the elements in the array.

5:31

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution