⚡Flashcard Drill➔
NeetCode #323LC-1721MediumLinked List
← Back to All Problems

#323 · #1721 · Swapping Nodes in a Linked List(交换链表中的节点)

📌 Problem Statement & Constraints

You are given the head of a linked list and an integer k. Swap the values of the k-th node from the beginning and the k-th node from the end, and return the head. k is 1-indexed. Constraints: 1 <= n <= 10^5, 1 <= k <= n, 0 <= Node.val <= 100.

💡 Core Algorithmic Approaches

  1. Find the k-th node from the front by advancing k steps from a dummy head.
  2. Then advance a second pointer from the dummy until the first pointer reaches the end; the second pointer lands on the k-th node from the back.
  3. Swap the two values (the problem asks to swap values, not nodes).
  4. One pass after the initial k steps, O(1) space.

💻 Benchmark Python3 Implementation

class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        fast = slow = dummy
        for _ in range(k):             # fast -> k-th node from the front
            fast = fast.next
        first = fast
        while fast:                    # slow -> k-th node from the back
            fast = fast.next
            slow = slow.next
        second = slow
        first.val, second.val = second.val, first.val
        return head

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass.
💾 Space Complexity
O(1): two pointers.

⚠️ Interview Pitfalls & Follow-ups

  • Swapping the nodes instead of the values: the problem asks for a value swap, which is simpler and avoids relinking.
  • Using a 1-indexed loop range(k - 1): with the dummy head, advancing k steps lands exactly on the k-th node.
  • Forgetting the dummy head: the k = 1 case would need a special branch.
  • Assuming k <= n / 2: the two positions may overlap when k is the middle node, and the swap is then a no-op -- which is correct.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems