Coding Challenge: Swapping Nodes in a Linked List and Swap Nodes in Pairs

In today’s article, we are throwing it back to one of the first data structures that we learned; linked lists. See here for a refresher on linked lists and how to implement your own linked list in JavaScript. Now that we have had some LeetCode practice and a few easy + medium problems under our belts I thought it would be a good time for a refresher and cover some problems a bit more challenging than ‘Reversing a Linked List.’

The basics of linked lists are:

• They are a simple data structure made up of a piece of data and a ‘next’ pointer.
• They are uni-directional, only traverse via the next pointer.
• Insertion and Removal have an O(1) runtime, depending on where you are inserting/removing.
• Searching and Access in a linked list takes O(n) runtime

Problem 1:

‘Given a linked list, swap every two adjacent nodes and return the head’ — do not modify the node’s values only the pointers on the nodes themselves.

Now it seems fairly straightforward if we were given a linked list of [1, 2, 3, 4] we would want something along the lines of [2, 1, 4, 3] returned. But as with any of these code challenges it is easier said than done.

Our basic strategy will go as follows:

1. declare two copies of the head (the head is the root of the inputted linked list). We will call one current and the other result.
2. Using a while loop we will loop through the linked list performing the swaps.
3. Within the while loop, we will declare 2 more variables, next and temp. These two variables will make use of our logic to perform the swaps.
4. Once the while loop condition is no longer met (current && current.next) we will return the result which should have been a copy of the original head.

The core logic takes place within the while loop on lines 30–38. When the problem is boiled down, linked list problems come down to the management of pointers. I still get confused fairly often but that’s why we practice to improve a bit each day.

Problem 2:

Now that we have completed the first problem let’s take a look at the following:

‘You are given a linked list and an integer, n as an input. Return the head of the linked list after swapping the nth node from the beginning of the list as well as the nth node from the end.‘

Please see the following example for clarification.

Given: [1,2,3,4,5] and n = 2

Expected: [1,4,3,2,5]

Instead of swapping every other node, we are now selecting and swapping 2 node values which are n nodes away from the beginning and end of the list.

The strategy for this problem is as follows:

• Declare 3 copies of the head, clone, first, and second.
• The first loop we will use is a for loop, the conditions being: for (let i = 1; i < n; i++){}. Within this loop, we will traverse down the clone and second list copies. At the end of this loop we will be n nodes away from the beginning, and the second.value is what we were looking for.
• The next loop will be a while loop since we do not know for long the input list is. Conditions: while(clone.next){}. Within this loop, we will now continue traversing down the clone copy as well as the first copy. Once the copy clone reaches the end the first clone will be n nodes away from the end of the list as we made sure the clone copy was n nodes ahead in the first loop. We can now take the first.value and use it for our swap.
• The final part of this problem is to perform a simple swap and return the original head.

The explanation was a bit wordy — but please take the time to review the logic within the swapK function. I made use of a dummy list that led the way for my other 2 copies. Once I acquired the values that I needed to switch it was a simple swap in lines 44–46 and I returned the original head.

Thank you for joining me this week in reviewing some medium-level linked lists problems. Be sure to leave your approaches and any comments or calps are greatly appreciated!