eagertoLearn eagertoLearn - 5 months ago 40
Java Question

swap pair elements in linked list implemented in Java

I have written a code to

swap
elements of
linkedList
in
Java
.
Currently, my code fails, i.e., it is not
swapping
elements. I am having difficulty
on how to approach to this problem. Any tips?

public void switchPairs(){
if (front==null || front.next==null)
return ;
ListNode temp=front;
front=front.next;
ListNode curr=front;
while(curr.next!=null){
ListNode dummy = curr.next;
curr.next=temp;
temp.next=dummy;
temp=temp.next;
curr=dummy;
}
}

Input : front -> [3] -> [7] -> [4] -> [9] -> [8] -> [12] /
Expected output: front -> [7] -> [3] -> [9] -> [4] -> [12] -> [8] /
my output: front -> [7] -> [3] -> [4] -> [9] -> [8] -> [12] /

Answer

The way I approach this problem is

  1. Draw the linkedList for the input and desired output in the right format for the simplest case. Here I would start with 4 nodes;

  2. Then tackle the easy cases such as if the ListNode or the next is null

  3. On the paper, mark the links that are broken and that are formed. Note you have to do the breaking and linking in right order; Make sure you have reference to the nodes whose link you are breaking. otherwise you might end up losing some nodes. That is the whole crux here. Draw after each step when a node is broken or a link is formed. In this way, you can keep track of what is going;

  4. Translate what you have drawn on paper to code. That must be fairly straightforward! Often you would need to have temporary pointers to traverse the list;

  5. In this example, the front or head pointer needs to be changed. so I would do the first swap outside an iteration. The remaining changes I would inside a while loop.

  6. write a convienient toString method that can help you track the variables at each stage. I found it harder to use debuggers forrecusions and linkedLists. but that is just me.

Regarding the solution for this problem: This is not as easy problem in my opinion. but a good one to get a good grasp of linkedLists andPointers`

here is my solution:

public void switchPairs(){
    if (front==null || front.next==null)
        return ;
    //keep a pointer to next element of front
    ListNode current=front.next;
    //make front point to next element
    front.next=current.next;
    current.next=front;
    front=current;
    //current has moved one step back it points to first.
    //so get it to the finished swap position
    current=current.next;
    while(current.next!=null && current.next.next!=null){
        ListNode temp = current.next.next;
        current.next.next=temp.next;
        temp.next=current.next;
        current.next=temp;
        current=temp.next;
    }
}