What is the time complexity of Swapping Nodes in a Linked List?

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

What data structures are used to solve Swapping Nodes in a Linked List?

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

What are the key insights for solving Swapping Nodes in a Linked List?

Insight 1: We need to find both the k-th node from the beginning and the k-th node from the end without knowing the list's length beforehand. Insight 2: A two-pointer technique can efficiently find the k-th node from the end in a single pass after finding the k-th node from the beginning.

Which companies ask LeetCode 1721. Swapping Nodes in a Linked List in interviews?

This problem is frequently asked at Nvidia, Snowflake.

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

Swapping Nodes in a Linked List - LeetCode 1721 Solution

Q: How to solve Swapping Nodes in a Linked List?

The solution utilizes a two-pointer approach to efficiently find both nodes to be swapped. First, it finds the k-th node from the beginning. Then, it uses two pointers, one starting from the head and the other starting from the k-th node from the beginning. By advancing both pointers until the second pointer reaches the end of the list, the first pointer will be pointing to the k-th node from the end. Finally, the values of the two nodes are swapped.

Swapping Nodes in a Linked List - Complete Solution Guide

Swapping Nodes in a Linked List is LeetCode problem 1721, 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

You are given the head of a linked list, and an integer k . Return the head of the linked list after swapping the values of the k th node from the beginning and the k th node from the end (the list is 1-indexed ). Example 1: Input: head = [1,2,3,4,5], k = 2 Output: [1,4,3,2,5] Example 2: Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5 Output: [7,9,6,6,8,7,3,0,9,5] Constraints: The number of nodes in the list is n . 1 <= k <= n <= 10 5 0 <= Node.val <= 100

Detailed Explanation

The problem asks us to swap the values of the k-th node from the beginning of a linked list with the k-th node from the end of the same linked list. The linked list is 1-indexed, meaning the first node is at index 1. The input is the head of the linked list and an integer k. The output is the head of the modified linked list after the swap.

Solution Approach

The solution utilizes a two-pointer approach to efficiently find both nodes to be swapped. First, it finds the k-th node from the beginning. Then, it uses two pointers, one starting from the head and the other starting from the k-th node from the beginning. By advancing both pointers until the second pointer reaches the end of the list, the first pointer will be pointing to the k-th node from the end. Finally, the values of the two nodes are swapped.

Step-by-Step Algorithm

Step 1: Initialize a pointer 'right' to the head of the linked list.
Step 2: Move the 'right' pointer 'k-1' steps forward to locate the k-th node from the beginning. Store this node in 'node1'.
Step 3: Initialize a pointer 'left' to the head of the linked list.
Step 4: Move both 'left' and 'right' pointers forward simultaneously until the 'right' pointer reaches the last node of the list (right.next == NULL).
Step 5: At this point, the 'left' pointer will be pointing to the k-th node from the end of the list. Store this node in 'node2'.
Step 6: Swap the values of 'node1' and 'node2'.
Step 7: Return the head of the linked list.

Key Insights

Insight 1: We need to find both the k-th node from the beginning and the k-th node from the end without knowing the list's length beforehand.
Insight 2: A two-pointer technique can efficiently find the k-th node from the end in a single pass after finding the k-th node from the beginning.
Insight 3: We only need to swap the *values* of the nodes, not the nodes themselves, which simplifies the process.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Linked List, Two Pointers.

Companies

Asked at: Nvidia, Snowflake.

Swapping Nodes in a Linked List | LeetCode 1721

Medium

Linked List Two Pointers

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 swapNodes(ListNode head, int k) {
        ListNode right = head;
        for (int i = 0; i < k - 1; i++) {
            right = right.next;
        }
        
        ListNode node1 = right;
        
        ListNode left = head;
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }
        
        ListNode node2 = left;
        
        int temp = node1.val;
        node1.val = node2.val;
        node2.val = temp;
        
        return head;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1721: Swapping Nodes in a Linked List - Detailed explanation and solution approaches.

Topics

Linked List Two Pointers

Companies

NvidiaSnowflake

Stats

Difficulty:Medium

Languages:4

Companies:2

Problem #:1721

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: Initialize a pointer 'right' to the head of the linked list.
2
Step 2: Move the 'right' pointer 'k-1' steps forward to locate the k-th node from the beginning. Store this node in 'node1'.
3
Step 3: Initialize a pointer 'left' to the head of the linked list.
4
Step 4: Move both 'left' and 'right' pointers forward simultaneously until the 'right' pointer reaches the last node of the list (right.next == NULL).
5
Step 5: At this point, the 'left' pointer will be pointing to the k-th node from the end of the list. Store this node in 'node2'.
6
Step 6: Swap the values of 'node1' and 'node2'.
7
Step 7: Return the head of the 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 algorithm iterates through the linked list at most twice: once to find the k-th node from the beginning and then again to find the k-th node from the end. Since the number of operations is proportional to the number of nodes, the time complexity is O(n). The algorithm uses a fixed number of pointers, regardless of the size of the linked list, resulting in O(1) space complexity.

📖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

Store the linked list in an array.

Traverse the linked list and store the values in an array. Then swap the elements at index k-1 and n-k. Finally, recreate the linked list with swapped values.

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

Trade-offs: This approach uses extra space to store the linked list in an array. It is not ideal when memory usage is a concern. The original approach is more efficient in terms of space complexity.

✨

Key Insights

1Insight 1: We need to find both the k-th node from the beginning and the k-th node from the end without knowing the list's length beforehand.
2Insight 2: A two-pointer technique can efficiently find the k-th node from the end in a single pass after finding the k-th node from the beginning.
3Insight 3: We only need to swap the *values* of the nodes, not the nodes themselves, which simplifies the process.

📚

Key Terms Explained

For Students

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Linked List

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

Edge Cases

Edge case 1: k = 1 (swap first and last node). The algorithm handles this correctly as the loop and while condition will still execute, and the left and right pointers will traverse accordingly.
Edge case 2: k = n (swap last and first node). The algorithm correctly identifies the first and last nodes and swaps their values.
Edge case 3: Single node linked list (n=1). If k=1, the while loop will not be executed and node1 and node2 will both point to the head. Swapping the value of the head with itself has no effect, so the algorithm works.
Edge case 4: k > n (invalid input, but constraints specify that 1 <= k <= n, so we don't need to explicitly handle it.)

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Modifying the `next` pointers instead of just swapping the values. This changes the entire structure of the linked list and is not what the problem asks for.

✗Common mistake 2: Incorrectly calculating the k-th node from the end. The two-pointer approach must be implemented carefully to ensure correct node selection.

✗Common mistake 3: Off-by-one errors when iterating with `k` to find the k-th node from the beginning or the end.

✅

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: Data manipulation in memory-constrained environments. The O(1) space complexity makes this approach suitable for systems with limited memory.

🏦Real-world scenario 2: Implementing undo/redo functionality where you might need to swap states based on their relative positions in a history list (represented as a linked list).

💡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

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ 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: September 10, 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

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 29

❓

Frequently Asked Questions

How does the fast/slow pointer technique work?

Fast pointer moves 2 steps while slow moves 1 step. When fast reaches the end, slow is at middle. If there's a cycle, they will meet. This technique is used for: finding middle node, detecting cycles, finding cycle start point, and checking palindromes.

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Swapping Nodes in a Linked List"?

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 two pointers techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?