24. Swap Nodes in Pairs

Swap Nodes in Pairs (LeetCode 24) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Linked List Manipulation Patterns pattern, in the Reordering / Partitioning subpattern.

How to solve Swap Nodes in Pairs

Swap Nodes in Pairs is a Linked List Reordering and Partitioning problem, part of Linked List Manipulation Patterns. Learn to reorder and partition linked lists. Master techniques like swap pairs, rotate list, and odd-even separation.

Work towards the solution in these steps:

1. Consider how linked lists can be manipulated by changing node pointers rather than node values.
2. Think about traversing the list in pairs, and how you might swap two adjacent nodes by adjusting their next pointers.
3. How can you keep track of the previous node to reconnect the swapped pairs properly?

The reference solution runs in O(n) time and O(1) space.

The Swap Nodes in Pairs solution and editorial walks through the full approach with reference code.

Problem statement

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]

Output: [2,1,4,3]

Explanation:

Example 2:

Input: head = []

Output: []

Example 3:

Input: head = [1]

Output: [1]

Example 4:

Input: head = [1,2,3]

Output: [2,1,3]

Constraints:

- The number of nodes in the list is in the range [0, 100].

- 0 <= Node.val <= 100

Topics and companies

Topics: Linked List, Recursion.

Reported in interviews at Microsoft, Amazon, Facebook, Google, eBay, ByteDance.

How to practise Swap Nodes in Pairs on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Swap Nodes in Pairs in the code editor, or read the Swap Nodes in Pairs editorial for a worked solution with its approach and complexity analysis.

Where Swap Nodes in Pairs sits in the DSA pattern sheet

• Linked List Manipulation Patterns pattern guide
• Reordering / Partitioning subpattern
• The full DSA patterns sheet

Problems related to Swap Nodes in Pairs

Other problems that use the same Reordering / Partitioning and Linked List Manipulation Patterns techniques:

• Insert Greatest Common Divisors in Linked List — Medium, same subpattern
• Odd Even Linked List — Medium, same subpattern
• Partition List — Medium, same subpattern
• Reorder List — Medium, same subpattern
• Rotate List — Medium, same subpattern
• Add Two Numbers — Medium, same pattern

Swap Nodes in Pairs FAQ