052.md

1721. Swapping Nodes in a Linked List

Difficulty: 🟡 Medium

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).

Examples:

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

Solutions

O(n) solution

# 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]:
        pointer = head
        for _ in range(k-1):
            pointer = pointer.next

        left_node = pointer
        right_node = head

        while pointer.next:
            pointer = pointer.next
            right_node = right_node.next

        left_node.val, right_node.val = right_node.val, left_node.val

        return head

The given solution approach swaps the values of the k-th node from the beginning and the k-th node from the end in a linked list. It follows these steps:

1. Traverse the linked list to find the k-th node from the beginning and store it in left_node.
2. Initialize two pointers, left_node and right_node, both pointing to the head of the linked list.
3. Move the right_node pointer to the (n - k)-th node from the beginning, where n is the length of the linked list.
4. Swap the values of left_node.val and right_node.val.
5. Return the head of the modified linked list.

Complexity Analysis

The time complexity of the algorithm is O(n) since it requires traversing the linked list twice: once to find the k-th node from the beginning and once to find the (n - k)-th node from the beginning.

The space complexity of the algorithm is O(1) since it uses a constant amount of additional space.

Summary

The given solution swaps the values of the k-th node from the beginning and the k-th node from the end in a linked list. It traverses the linked list twice, swaps the values, and returns the head of the modified linked list. The algorithm has a time complexity of O(n) and a space complexity of O(1).

NB: If you want to get community points please suggest solutions in other languages as merge requests.