💬 Discord
Sign In
NeetCode #330LC-24MediumLinked List
← Back to All Problems

#330 · #24 · Swap Nodes in Pairs(两两交换链表中的节点)

📌 Problem Statement & Constraints

Given a linked list, swap every two adjacent nodes and return its head. You must not modify the values in the nodes, only the nodes themselves may be changed. Constraints: the number of nodes is in [0, 100].

💡 Core Algorithmic Approaches

  1. Process the list two nodes at a time with a prev pointer that sits before the current pair.
  2. For a pair (first, second): point first.next at second.next, second.next at first, and prev.next at second.
  3. Then move prev to first, which is now the second node of the pair and the predecessor of the next pair.
  4. The dummy head handles the first pair without a special case. A single trailing node is left untouched by the loop condition.

💻 Benchmark Python3 Implementation

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy
        while prev.next and prev.next.next:   # a full pair exists
            first = prev.next
            second = first.next
            # rewire: prev -> second -> first -> rest
            first.next = second.next
            second.next = first
            prev.next = second
            prev = first                  # the new predecessor is the old first node
        return dummy.next

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each pair is processed once.
💾 Space Complexity
O(1): the nodes are relinked.

⚠️ Interview Pitfalls & Follow-ups

  • Swapping values instead of nodes: explicitly forbidden by the problem.
  • Forgetting to advance prev: the loop would reprocess the same pair and loop forever.
  • Advancing prev to second: second is now the head of the pair, so the correct predecessor of the next pair is first.
  • Not handling an odd-length list: the loop condition prev.next and prev.next.next leaves the trailing node alone.