Hello again everyone! Been sometime since I wrote here.
Today I wanted to take a peek at a simple Linked List problem – Swap Node Pairs. Took me a bout 5 mins to write it out so it should be a cup of tea!
Given a Linked List, we want to swap every two adjacent nodes and return the head. (i.e. given 1->2->3->4 we want to return 2->1->4->3). There is one tiny catch to it. To make sure we demonstrate our knowledge in pointers, we are going to try to use only constant space.
The first thing we need to do is make sure we remove any ambiguities. It is not specified whether in our Swap Node Pairs problem, the Linked List is a Singly Linked List or a Doubly Linked List. Hence we should absolutely ask in an interview situation. For the purpose of our solution we are going to assume our interviewer wants to know about a Doubly Linked List.
Below is the solution in Java:
Swap Node Pairs – Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
/* * @Author: Ajk Palikuqi * * @Question: Swap Node Pairs - Given a Linked List swap its adjacent nodes. * */ package IQLib.LinkedListLib; public class SwapNodePairs { // Uses constant space public static void SwapAdjacentNodes(LinkedListNode head) { if (head == null || head.getNext() == null) { return head; } LinkedListNode newHead = head.getNext(); while (head != null && head.getNext() != null) { LinkedListNode currNext = head.getNext(); currNext.setPrevious(head.getPrevious()); head.setPrevious(currNext); head.setNext(currNext.getNext()); currNext.setNext(head); head = head.getNext(); } return newHead; } } |
There it is. Obviously our Swap Node Pairs solution runs in linear time (if you have problem calculating that, check some of my very first posts). Hope you guys enjoyed it… and I’ll see you guys next time ;D.
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017