Leetcode 24: Swap Nodes in Pairs

1. Problem Statement (Simple Explanation):

You are given the head of a singly linked list.

You must swap every two adjacent nodes and return the new head.

You cannot modify the node values; you must change the links (i.e., rearrange nodes).
If the list has an odd number of nodes, the last node stays where it is.

2. Examples:

Example 1:

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

Pairs to swap:

(1, 2) → becomes (2, 1)
(3, 4) → becomes (4, 3)

Output: [2,1,4,3]

Example 2:

Input: head = []

Output: []

Example 3:

Input: head = [1]

Only one node → no swap.

Output: [1]

Example 4:

Input: head = [1,2,3]

Pairs:

(1, 2) → (2, 1)
3 stays as is.

Output: [2,1,3]

3. Approach 1 – Iterative Pointer Manipulation (Dummy Node):

We’ll swap every pair of nodes by adjusting .next pointers.

Intuition:

Use a dummy node to simplify handling the head. Then, for each pair:

Suppose we have:

prev -> first -> second -> nextPairStart

We want to transform it to:

prev -> second -> first -> nextPairStart

Steps to swap:

prev.next = second
first.next = second.next (which is nextPairStart)
second.next = first

Then move prev to first and continue with the next pair.

Algorithm (Step-by-Step):

Create dummy = new ListNode(0) and set dummy.next = head.
Set prev = dummy.
While prev.next != null and prev.next.next != null:

first = prev.next
second = prev.next.next
Perform the swap:

prev.next = second
first.next = second.next
second.next = first

Move prev = first (since first is now the second node in the pair).

Return dummy.next as the new head.

Pseudo-code (Iterative):

Complexity:

Let n be the length of the list:

Time: O(n) (each node is visited a constant number of times).
Space: O(1) extra.

4. Approach 2 – Recursive (Optional):

You can also solve this recursively:

Base cases:

head == null or head.next == null → return head.

Recursive step:

first = head
second = head.next
Recursively swap the rest starting from second.next:

first.next = swapPairs(second.next)

Then make second the new head of this pair:

second.next = first

Return second.

The recursive idea is elegant but uses recursion stack space O(n).

5. Java code:

6. C code:

7. C++ code:

8. Python code:

9. JavaScript code:

Comments

Leetcode 1: Two Sum

Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to return the indices of two numbers in the array such that: Conditions: Each input has exactly one solution . You cannot use the same element twice . You can return the answer in any order . 2. Examples Example 1 Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: nums[0]+nums[1]=2+7=9 So we return [0, 1]. Example 2 Input: ...

Leetcode 3: Longest Substring Without Repeating Characters

Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input: s = "pwwkew" Output: 3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a single digit . The digits are stored in reverse order (i.e., the 1’s digit is at the head). You need to add the two numbers and return the sum as a linked list , also in reverse order. You can assume: There are no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input: l1 = [2,4,3] l2 = [5,6,4] Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output: [7,0,8] Explanation: ...

codesprint with rishav

Search This Blog