{x}
blog image

Swapping Nodes in a Linked List

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 kth node from the beginning and the kth 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 <= 105
  • 0 <= Node.val <= 100

Solution Explanation: Swapping Nodes in a Linked List

This problem requires swapping the nodes at the kth position from the beginning and the kth position from the end of a linked list. The solution uses a two-pointer approach for efficiency.

Approach:

  1. Find the kth node from the beginning: We use a fast pointer to traverse the linked list until it reaches the kth node. This pointer is then stored as p.

  2. Find the kth node from the end: Simultaneously, we use a slow pointer starting at the head. While the fast pointer traverses to the end of the list, the slow pointer moves such that when fast reaches the tail, slow will point to the kth node from the end. This pointer is stored as q.

  3. Swap the values: Finally, we swap the val (data) of the nodes pointed to by p and q. We do not physically swap the nodes themselves, as that would involve changing pointers and is more complex. Swapping the values is sufficient to fulfill the problem requirements.

  4. Return the head: The head of the linked list remains unchanged, so we return the original head.

Time Complexity: O(n), where n is the number of nodes in the linked list. This is because we traverse the list once to find both the kth node from the beginning and the kth node from the end.

Space Complexity: O(1). The algorithm uses only a constant amount of extra space to store the pointers.

Code Examples (Python, Java, C++, Go, TypeScript, C#):

The provided code snippets demonstrate the solution in various programming languages. Each implements the two-pointer approach described above. The core logic is consistent across all implementations. Note that the ListNode definition (representing a node in the linked list) may vary slightly depending on the language.

Example (Python):

class Solution:
    def swapNodes(self, head: ListNode, k: int) -> 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

This Python code concisely demonstrates the algorithm. The for loop finds p, and the while loop finds q, after which the values are swapped.

The other language examples (Java, C++, Go, TypeScript, C#) follow a similar structure, adapting the syntax and data structures to their respective languages, but maintaining the core two-pointer approach and O(n) time and O(1) space complexity.