DSA Visualizations | Hello Interview

Swap Nodes in Pairs

DESCRIPTION (credit Leetcode.com)

Given a reference head of type ListNode that is the head of a singly linked list, write a function to 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.)

EXAMPLES

Example 1: input:

output:

Explanation: 5 and 4 are swapped, 3 and 2 are swapped, and 1 is left alone.

Example 2: input:

output:

Explanation: 1 and 2 are swapped, 3 and 4 are swapped.

Solution

Since we can't modify the values in the nodes, our function needs to swap the nodes by traversing the list and updating the next pointers of the nodes.

This question is an example of how using a dummy node simplifies a solution by removing the need for special logic for swapping the first two nodes in the list. To understand why, let's first look at how to swap a pair of nodes in a linked list.

Let's say we want to swap the pair of nodes first and second in the linked list below:

We need to perform 3 operations:

1). Since we need the node before first to point to second instead of first, we need a pointer prev which references the node before first. Then, we can update prev.next to point to second.

2). We need to update first.next to point to second.next.

3). Finally, we need to update second.next to point to first.

Once that is complete, we can move to the next pair of nodes to swap.

Need for a Dummy Node

As we just saw, swapping a pair of nodes requires a pointer to node before the first node in the pair we want to swap. This is not a problem when we are swapping nodes in the middle of the list, but it is when we are swapping the first pair of nodes in the list because there is no node before head!

We fix this by introducing a dummy node that points to the head of the list. This guarantees that each node in the original list has a node before it, meaning we can swap all nodes in the list using the same logic.


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

swap nodes in pairs

0 / 1

From there, we can initialize two pointers, prev and first. first will point to the first node in the pair we want to swap, and prev points to the node before first, which is the dummy node to start. We also initialize the pointer second to point to the node after first.


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

0 / 2

We then perform the same 3 operations we discussed earlier to swap the pair of nodes:

1). Update prev.next to point to second. 2). Update first.next to point to second.next. 3). Update second.next to point to first.


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

0 / 2

Now, with first and second swapped, we move prev and first to prepare for the next iteration. first now points to the node right before the next pair of nodes, so we update prev to point to first and first to point to first.next. After that, we update second to point to first.next, and our pointers are in the same state to perform the same 3 operations to swap the next pair of nodes.


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

0 / -1

Termination

We can stop the loop when first is None, or when first.next is None. When there an even number of nodes in the list, first will be None when all pairs of nodes have been swapped. When there is an odd number of nodes, first.next will be None when first is at the last node in the list, which we can't swap.

After the loop terminates, we return dummy.next, which is the head of the list with all pairs of nodes swapped.


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

0 / -1

Code

To construct the linked list that is used in the animation below, provide a list of integers nodes. Each integer in nodes is used as the value of a node in the linked list, and the order of the integers in nodes will be the order of the nodes in the linked list.

For example, if nodes = [1, 2, 3], the linked list will be 1 -> 2 -> 3.


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

swap nodes in pairs

0 / 5

Edge Cases

Empty List

When the list is empty, head is None. The while loop never runs, and we return dummy.next, which is equal to None.


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

swap nodes in pairs

0 / 5

head = []

One Node

When there is only one node in the list, first is the only node in the list, and first.next is None. The while loop never runs, and we return dummy.next, which is head with the single node.


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

swap nodes in pairs

0 / 5

head = [1]

Two Nodes

When there are two nodes in the list, first is the first node, and second is the second node. The while loop runs once to swap the two nodes, after which fast is None so the loop terminates. We return dummy.next, which is the head of the list with the two nodes swapped.


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

swap nodes in pairs

0 / 5

head = [1, 2]

Complexity Analysis

Time Complexity: O(N) where N is the number of nodes in the list. We visit each node in the list once, and perform the same number of operations at each node.

Space Complexity: O(1). We only use a constant amount of extra space to store the pointers prev, first, and second.

Next: Overview

Your account is free and you can post anonymously if you choose.

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Reorder List

Binary Search: Overview

Swap Nodes in Pairs

DESCRIPTION (credit Leetcode.com)

Given a reference head of type ListNode that is the head of a singly linked list, write a function to 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.)

EXAMPLES

Example 1: input:

output:

Explanation: 5 and 4 are swapped, 3 and 2 are swapped, and 1 is left alone.

Example 2: input:

output:

Explanation: 1 and 2 are swapped, 3 and 4 are swapped.

Solution

Since we can't modify the values in the nodes, our function needs to swap the nodes by traversing the list and updating the next pointers of the nodes.

Let's say we want to swap the pair of nodes first and second in the linked list below:

We need to perform 3 operations:

1). Since we need the node before first to point to second instead of first, we need a pointer prev which references the node before first. Then, we can update prev.next to point to second.

2). We need to update first.next to point to second.next.

3). Finally, we need to update second.next to point to first.

Once that is complete, we can move to the next pair of nodes to swap.

Need for a Dummy Node


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

swap nodes in pairs

0 / 1


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

0 / 2

We then perform the same 3 operations we discussed earlier to swap the pair of nodes:

1). Update prev.next to point to second. 2). Update first.next to point to second.next. 3). Update second.next to point to first.


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

0 / 2


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

0 / -1

Termination

After the loop terminates, we return dummy.next, which is the head of the list with all pairs of nodes swapped.


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

0 / -1

Code

For example, if nodes = [1, 2, 3], the linked list will be 1 -> 2 -> 3.


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

swap nodes in pairs

0 / 5

Edge Cases

Empty List

When the list is empty, head is None. The while loop never runs, and we return dummy.next, which is equal to None.


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

swap nodes in pairs

0 / 5

head = []

One Node

When there is only one node in the list, first is the only node in the list, and first.next is None. The while loop never runs, and we return dummy.next, which is head with the single node.


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

swap nodes in pairs

0 / 5

head = [1]

Two Nodes


def swapPairs(head):
  dummy = ListNode(0)
  dummy.next = head
  tail, first = dummy, head

  while first and first.next:
    second = first.next

    # swap nodes
    tail.next = second
    first.next = second.next
    second.next = first

    tail = first
    first = first.next

  return dummy.next

swap nodes in pairs

0 / 5

head = [1, 2]

Complexity Analysis

Time Complexity: O(N) where N is the number of nodes in the list. We visit each node in the list once, and perform the same number of operations at each node.

Space Complexity: O(1). We only use a constant amount of extra space to store the pointers prev, first, and second.

Next: Overview

Your account is free and you can post anonymously if you choose.

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103