Swapping Nodes in a Linked List

Tested Python solution for LeetCode 1721 with 24 pytest cases. Generate a practice environment with lcpy.

LeetCode 1721, Medium. Topics: Linked List, Two Pointers. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 24 parametrized pytest cases, and a playground notebook:

lcpy gen -n 1721   # by problem number
lcpy gen -s swapping_nodes_in_a_linked_list   # by problem name

​

Problem

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<sup>th</sup> node from the beginning and the k<sup>th</sup> node from the end (the list is 1-indexed).

​

Examples

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

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^5
• 0 <= Node.val <= 100

Follow up: Could you do this in one pass?

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from leetcode_py import ListNode


class Solution:
    # Time: O(n)
    # Space: O(1)
    def swap_nodes(self, head: ListNode[int] | None, k: int) -> ListNode[int] | None:
        if head is None:
            return head

        n = 1
        node = head
        while node.next is not None:
            node = node.next
            n += 1

        first = head
        for _ in range(k - 1):
            if first.next is None:
                break
            first = first.next

        second = head
        for _ in range(n - k):
            if second.next is None:
                break
            second = second.next

        first.val, second.val = second.val, first.val
        return head

​

Complexity

Time	Space
O(n)	O(1)

​

Tags

NeetCode All.