swap pair elements in linked list implemented in Java

Question

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 1

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;
    }
}

Answer 2

The best way to answer a question like this to to visualize the state of your list as it progresses thru the iteration. I have implemented the code with a println to help with that. The other choice is to include variable names that are easier to keep track of, while temp and dummy will not prevent you from achieving correctness they are more difficult to follow.

This is the function

    public ListNode switchPairs(){
        if (this==null || this.next==null)
            return this;
        ListNode top = this.next;

        ListNode first = this;
        ListNode second = first.next;

        do {
            ListNode third = second.next;
            second.next = first;
            first.next = third;
            first = third;
            System.out.println("@@@ " + top.toString());
            if (first != null) {
                // remember second now is really the first element on the list
                // at this point.
                second.next.next = first.next;
                second = first.next;
            }

        } while(first != null && second != null);

        return top;
    }

And this is the entire code

public class ListNode {
    private ListNode next = null;
    private final int i;
    ListNode(int i) {
        this.i = i;
    }

    ListNode(int i, ListNode parent) {
        this(i);
        parent.next = this;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[" + this.i + "]");
        if (this.next != null) {
            sb.append("->");
            sb.append(this.next.toString());
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        ListNode top = null;
        ListNode curr = null;
        for(String arg : args) {
            int i = Integer.parseInt(arg);
            if(curr == null) 
                curr = new ListNode(i);
            else
                curr = new ListNode(i, curr);
            if( top == null) 
                top = curr;
        }
        System.out.println(top.toString());
        top = top.switchPairs();
        System.out.println(top.toString());
    }

    public ListNode switchPairs(){
        if (this==null || this.next==null)
            return this;
        ListNode top = this.next;

        ListNode first = this;
        ListNode second = first.next;

        do {
            ListNode third = second.next;
            second.next = first;
            first.next = third;
            first = third;
            System.out.println("@@@ " + this.toString());
            if (first != null) {
                second.next.next = first.next;
                second = first.next;
            }

        } while(first != null && second != null);

        return top;
    }
}

Last but not least a sample output

java ListNode 1 2 3 4 5 6 7 8
[1]->[2]->[3]->[4]->[5]->[6]->[7]->[8]
@@@ [2]->[1]->[3]->[4]->[5]->[6]->[7]->[8]
@@@ [2]->[1]->[4]->[3]->[5]->[6]->[7]->[8]
@@@ [2]->[1]->[4]->[3]->[6]->[5]->[7]->[8]
@@@ [2]->[1]->[4]->[3]->[6]->[5]->[8]->[7]
[2]->[1]->[4]->[3]->[6]->[5]->[8]->[7]

Answer 3

public void switchPairs() {
   ListNode prev = front;
    if(front!=null && front.next != null) {
        ListNode temp = front;
        front = front.next;
        temp.next = front.next;
        front.next = temp;
        prev = temp;
    }
    while(prev !=null && prev.next != null && prev.next.next != null) {
        ListNode first_node =prev.next;
        ListNode second_node = first_node.next;
        first_node.next = second_node.next;
        second_node.next = first_node;
        prev.next = second_node;
        prev = first_node;
    }
}

Answer 4

// Recursive solution
public void switchPairs(SingleLinkListNode prev, SingleLinkListNode node) {

    if (node == null || node.next == null) {
        return;
    }
    SingleLinkListNode nextNode = node.next;
    SingleLinkListNode temp = nextNode.next;
    nextNode.next = node;
    node.next = temp;
    if (prev != null) {
        prev.next = nextNode;
    } else {
        head = nextNode;
    }

    switchPairs(node, node.next);
}

Answer 5

I have this recursive function, which works:

    public void swap2List(){
    root = swap2List(root);   //pass the root node
    }   
    private Node swap2List(Node current){
    if(current == null || current.next == null){
    return current;
    }
    else{
    Node temp = current;
    Node temp2 = current.next.next;
    current = current.next;
    current.next = temp;
    temp.next = swap2List(temp2);       
    } 
    return current;
    }

Answer 6

public static LinkedList<Integer> switchPairs(LinkedList list) { ListIterator<Integer> iterator = list.listIterator(); LinkedList<Integer> out = null; while (iterator != null && iterator.hasNext()) { if (out == null) { out = new LinkedList<Integer>(); } int temp = iterator.next(); if (iterator.hasNext()) { out.add(iterator.next()); out.add(temp); }else{ out.add(temp); } } return out; }