DEV Community

Cover image for Code 101: Swap Nodes in Pairs
Garvit Khamesra
Garvit Khamesra

Posted on

Code 101: Swap Nodes in Pairs

Question:

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]

Example 2:

Input: head = [] Output: []

Example 3:

Input: head = [1] Output: [1]

 

Constraints:

  • The number of nodes in the list is in the range [0, 100].
  • 0 <= Node.val <= 100

You can find the question here.

Solution:

This question can be solved with both iterative and recursive approaches, But As I'm covering recursion so will start with the recursive approach and then will explain the iterative approach.

Recursive approach

  1. The Base Condition
  2. What to do, to get a solution?
  3. Recursive call

I broke down the solution in these steps.

Now the 1st step is pretty straightforward. As we know, to swap 2 nodes we need 2 nodes, so let's say we have 2 null checks for that. And for step 3, Can we consider moving to the next node by skipping 1 node? So that we cover every node.

Now coming to 2nd point.

We know that to swap we need to have 2 nodes, and for swapping we make changes to the next pointer in the list.

Because we are trying to solve it through recursion, for me the problem is to visualize the solution, so I have tried to show using some diagrams.

Let's take an example of list

1-> 2 -> 3-> 4

Recursive Approach

Now with this example, you should a rough idea of the algorithm. We will use the same logic to code.

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }

Iterative Approach

Iterative approach

So if you view the above image it follows a similar approach just we need an additional node.

public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode current = dummy;
    while (current.next != null && current.next.next != null) {
        ListNode first = current.next;
        ListNode second = current.next.next;
        first.next = second.next;
        current.next = second;
        current.next.next = first;
        current = current.next.next;
    }
    return dummy.next;
}

#HappyCoding

Top comments (0)