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
- Find the
k-th node from the front by advancingksteps from a dummy head. - 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. - Swap the two values (the problem asks to swap values, not nodes).
- One pass after the initial
ksteps, 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, advancingksteps lands exactly on thek-th node. - Forgetting the dummy head: the
k = 1case would need a special branch. - Assuming
k <= n / 2: the two positions may overlap whenkis 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.