What is the time complexity of Swap Nodes in Pairs?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Swap Nodes in Pairs?

This problem uses Linked List, Recursion. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Swap Nodes in Pairs?

Insight 1: The core of the solution lies in manipulating the 'next' pointers of the nodes to achieve the swapping without actually changing their values. Insight 2: Using a dummy node simplifies the handling of the head of the list, especially when the first pair needs to be swapped, as it provides a stable starting point.

Which companies ask LeetCode 24. Swap Nodes in Pairs in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Bloomberg, Meta and 6 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Swap Nodes in Pairs - LeetCode 24 Solution

Q: How to solve Swap Nodes in Pairs?

The solution uses an iterative approach to traverse the linked list, swapping pairs of nodes as it goes. A dummy node is introduced to simplify the handling of the list's head. The algorithm maintains a 'prev' pointer that always points to the node before the current pair being swapped. The 'next' pointers of 'prev', 'first_node', and 'second_node' are then re-assigned to effect the swap. 'prev' is then moved forward to the 'first_node' to process the next pair.

Swap Nodes in Pairs - Complete Solution Guide

Swap Nodes in Pairs is LeetCode problem 24, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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

Detailed Explanation

The problem asks us to swap every two adjacent nodes in a linked list without modifying the values stored in the nodes. We are only allowed to rearrange the nodes themselves. The input is the head of the linked list, and the output is the head of the modified linked list with nodes swapped in pairs.

Solution Approach

The solution uses an iterative approach to traverse the linked list, swapping pairs of nodes as it goes. A dummy node is introduced to simplify the handling of the list's head. The algorithm maintains a 'prev' pointer that always points to the node before the current pair being swapped. The 'next' pointers of 'prev', 'first_node', and 'second_node' are then re-assigned to effect the swap. 'prev' is then moved forward to the 'first_node' to process the next pair.

Step-by-Step Algorithm

Step 1: Create a dummy node and set its 'next' pointer to the original head of the linked list. This simplifies handling the case where the head of the list needs to be changed.
Step 2: Initialize a 'prev' pointer to the dummy node. This pointer is used to keep track of the node before the pair being swapped.
Step 3: Iterate through the linked list while 'prev.next' and 'prev.next.next' are not null. This ensures that there are at least two nodes to swap.
Step 4: Inside the loop, identify the first node ('first_node') as 'prev.next' and the second node ('second_node') as 'first_node.next'.
Step 5: Perform the swap by reassigning the 'next' pointers: 'prev.next' points to 'second_node', 'first_node.next' points to 'second_node.next', and 'second_node.next' points to 'first_node'.
Step 6: Move the 'prev' pointer to 'first_node' to prepare for the next swap.
Step 7: After the loop finishes, return 'dummy.next', which is the head of the modified linked list.

Key Insights

Insight 1: The core of the solution lies in manipulating the 'next' pointers of the nodes to achieve the swapping without actually changing their values.
Insight 2: Using a dummy node simplifies the handling of the head of the list, especially when the first pair needs to be swapped, as it provides a stable starting point.
Insight 3: The solution needs to carefully handle edge cases where the list is empty or contains only one node, and when the list has an odd number of nodes.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Linked List, Recursion.

Companies

Asked at: Adobe, Amazon, Apple, Bloomberg, Meta, Microsoft, Nutanix, Qualcomm, Snowflake, TikTok, Uber.

Swap Nodes in Pairs | LeetCode 24

Medium

Linked List Recursion

Time: O(n)Space: O(1)

Solution Code

Available in:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;

        while (prev.next != null && prev.next.next != null) {
            ListNode first_node = prev.next;
            ListNode second_node = first_node.next;

            // Swapping nodes
            prev.next = second_node;
            first_node.next = second_node.next;
            second_node.next = first_node;

            // Move prev to the node before the next pair
            prev = first_node;
        }

        return dummy.next;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 24: Swap Nodes in Pairs - Detailed explanation and solution approaches.

Topics

Linked List Recursion

Companies

AdobeAmazonAppleBloombergMetaMicrosoftNutanixQualcomm

Stats

Difficulty:Medium

Languages:4

Companies:11

Problem #:24

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Create a dummy node and set its 'next' pointer to the original head of the linked list. This simplifies handling the case where the head of the list needs to be changed.
2
Step 2: Initialize a 'prev' pointer to the dummy node. This pointer is used to keep track of the node before the pair being swapped.
3
Step 3: Iterate through the linked list while 'prev.next' and 'prev.next.next' are not null. This ensures that there are at least two nodes to swap.
4
Step 4: Inside the loop, identify the first node ('first_node') as 'prev.next' and the second node ('second_node') as 'first_node.next'.
5
Step 5: Perform the swap by reassigning the 'next' pointers: 'prev.next' points to 'second_node', 'first_node.next' points to 'second_node.next', and 'second_node.next' points to 'first_node'.
6
Step 6: Move the 'prev' pointer to 'first_node' to prepare for the next swap.
7
Step 7: After the loop finishes, return 'dummy.next', which is the head of the modified linked list.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is linear because each node is visited exactly once. The space complexity is constant because only a fixed number of extra variables are used, irrespective of the linked list's size. No auxiliary data structures that scale with the input size are used.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Recursive Approach

A recursive solution can also be used to swap nodes in pairs. The base case is when the list is empty or has only one node. Otherwise, the first two nodes are swapped, and the function is called recursively on the rest of the list.

Time: O(n), where n is the number of nodes in the linked list.Space: O(n) in the worst case due to the recursion depth, where n is the number of nodes. In the best case, with tail-call optimization, it could be O(1).

Trade-offs: The recursive approach is generally less efficient in terms of space complexity compared to the iterative approach due to the call stack. However, it can be more elegant and easier to understand for some.

✨

Key Insights

1Insight 1: The core of the solution lies in manipulating the 'next' pointers of the nodes to achieve the swapping without actually changing their values.
2Insight 2: Using a dummy node simplifies the handling of the head of the list, especially when the first pair needs to be swapped, as it provides a stable starting point.
3Insight 3: The solution needs to carefully handle edge cases where the list is empty or contains only one node, and when the list has an odd number of nodes.

📚

Key Terms Explained

For Students

Recursion

A function that calls itself to solve smaller versions of the same problem.

Linked List

Elements connected via pointers. Like a chain where each link knows the next.

Edge Cases

Edge case 1: Empty list (head is null). The code correctly handles this case because the while loop condition 'prev.next and prev.next.next' will be false immediately, and the function will return the dummy node's next which is null.
Edge case 2: List with only one node. Similar to the empty list, the while loop condition will be false because 'prev.next.next' will be null, and the function will return the original head of the list, which is the correct output.
Edge case 3: List with an odd number of nodes. The while loop terminates when there are no longer two nodes to swap, leaving the last node untouched, which is the correct behavior.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to update the 'prev' pointer after each swap, leading to incorrect swapping of subsequent pairs.

✗Common mistake 2: Not handling the edge cases of an empty list or a list with only one node correctly.

✗Common mistake 3: Modifying node values instead of only swapping the nodes themselves, violating the problem constraint.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Image processing, where linked lists can represent image data and swapping nodes might be used for transformations or manipulations.

🏦Real-world scenario 2: Undo/redo functionality in text editors or other applications. Linked lists can store the history of actions, and swapping nodes might be used to reorder the history.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

The dummy node technique prevents edge cases. For cycle detection, Floyd's algorithm is the standard. Always handle empty list and single node cases.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Losing reference to nodes when modifying pointers. Use temporary variables to save references.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 25, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 14

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 7

❓

Frequently Asked Questions

Why use a dummy node in linked list problems?

A dummy node simplifies edge cases where the head might change (insertion/deletion at head) or when building a new list. Initialize dummy.next = head, work with dummy.next throughout, and return dummy.next at the end to handle all cases uniformly.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Swap Nodes in Pairs"?

For this medium-level Linked List problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether recursion techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?