Why doesn't this swap adjacent pairs of a LinkedList?

Question

public void swapPairs() {
    ListNode temp = this;
    ListNode dummy = this;

    while (temp.next != null) {
        temp.next = temp.next.next;
        dummy.next.next = temp;
        temp = temp.next;
        dummy = dummy.next;
    }
}

I'm essentially trying to use this method on a LL head node, and have it swap adjacent pairs such that (1,2,3,4) -> (2,1,4,3)

The logic of the method seems consistent to me but it's not working.

I hope you're not counting on that `dummy` being an actual copy of `this`. — Zircon, Feb 03 '17 at 15:08
@Zircon How would i modify it then? Does this = this.next change the node your working on? — Ben Arnao, Feb 03 '17 at 15:13
Somewhat related, although the OP isn't asking about pass-by: http://stackoverflow.com/q/40480/18356 — shoover, Feb 03 '17 at 15:22
The very first statement in your while loop severs the 2nd node from your LL without any possibility of getting it back. — David Choweller, Feb 03 '17 at 15:30
At the start of your loop, `temp` and `dummy` are both pointing to the same head node. Then you set the head node next pointer to `head.next.next`. The `dummy` node and the `temp` node are still pointing to the head node, but the 2nd node is lost because you overwrote the head node `next` field without saving it anywhere. — David Choweller, Feb 03 '17 at 16:36
Point your `dummy` node at `temp.next` (the second node) and _then_ modify the `temp.next.next` pointer. After this, you'll have `temp` pointing at the first node, and `dummy` pointing at the second, and both `temp` and `dummy`'s next pointers pointing at the third node (or `null` if there are only 2 nodes in the list). — David Choweller, Feb 03 '17 at 16:52
Then set `dummy.next` to point to `temp` (the first node). Then, since you want `dummy` to be the new first node, modify the head of the list (`this`?) to point to `dummy`. — David Choweller, Feb 03 '17 at 16:55

rcgldr · Accepted Answer · 2017-02-03T18:16:41.110

This is working:

    public void swap(){
        ListNode node1;
        ListNode node2;
        ListNode prev;
        prev = this;
        while(true){
            node1 = prev.next;
            if(node1 == null)
                break;
            node2 = node1.next;
            if(node2 == null)
                break;
            node1.next  = node2.next;
            node2.next  = node1;
            prev.next   = node2;
            prev        = node1;
        }
    }

Complete program:

package x;
class ListNode{
    ListNode next;
    int data;
    ListNode(){
        data = -1;
    }
    ListNode(int d){
        data = d;
    }
    public void append(int data) {
        ListNode newNode = new ListNode (data);
        if(this.next == null){
            this.next = newNode;
            return;
        }
        ListNode curr = this.next;
        while(curr.next != null)
            curr = curr.next;
        curr.next = newNode;
    }
    public void insert(int data) {
        ListNode newNode = new ListNode (data);
        newNode.next = this.next;
        this.next = newNode;
    }
    public void show(){
        ListNode node = this.next;
        while(node != null){
            System.out.println(node.data);
            node = node.next;
        }
        System.out.println();
    }
    public void swap(){
        ListNode node1;
        ListNode node2;
        ListNode prev;
        prev = this;
        while(true){
            node1 = prev.next;
            if(node1 == null)
                break;
            node2 = node1.next;
            if(node2 == null)
                break;
            node1.next  = node2.next;
            node2.next  = node1;
            prev.next   = node2;
            prev        = node1;
        }
    }
}


public class x {

    public static void main(String[] args) {
        ListNode head = new ListNode();
        head.append(4);
        head.append(5);
        head.append(6);
        head.append(7);
        head.insert(3);
        head.insert(2);
        head.insert(1);
        head.insert(0);
        head.show();
        head.swap();
        head.show();
    }
}

*this* would be the head node of a LL. I would also want to do this over any size LL, we can assume it has an even number of elements. — Ben Arnao, Feb 03 '17 at 15:48
still not working for. Maybe recursion is what should be done here? — Ben Arnao, Feb 03 '17 at 16:09
@BenArnao - I updated my answer to show a complete working example. — rcgldr, Feb 03 '17 at 17:52
Sorry if the answer is obvious, but how does it ever break out of the while loop? — Ben Arnao, Feb 03 '17 at 21:06
It uses `break`s. But it does not work. It stays where it is. — Grzegorz Górkiewicz, Feb 03 '17 at 21:34
@BenArnao - It breaks out of the while loop when it reaches the end of the list, when either node1 or node2 == null. You can try the code with this [online example](http://code.geeksforgeeks.org/9nYUAi) . Click on "run" to re-run the code and produce new output. — rcgldr, Feb 04 '17 at 00:34

David Choweller · Answer 2 · 2017-02-03T17:45:13.367

In the code below, I'm assuming that this is a pointer to the head node:

public void swapAdjacentNodes() {

    ListNode first = this;  // point first to head node

    if (first == null) {
        return;
    }


    ListNode prev = null; // Node behind 1st adjacent node

    ListNode second = first.next; // second points to the 2nd adj node

    while (second != null) {  // There are still pairs to swap

        first.next = second.next;  // Set 1st adj next to 3rd (or null)
        second.next = first;       // Set 2nd adj next to 1st

        if (prev==null) {  // If 1st adj was 1st in list
            this = second;   // point head to 2nd adj
        } else {
            prev.next = second;  // point prev next to new 1st of pair.
        }
        prev = first;            // prev now points to new 1st of pair. 
        first = first.next;        // move cur to 1st of next pair
        if (first==null) {       // if there's no pair, we're done
            break;
        }
        second = first.next;       // Point second to 2nd of next pair
    }

}

I tested it with lists of 0, 1,2, 4 and 5 elements and it worked for those cases. — David Choweller, Feb 03 '17 at 21:16
Yes, that's correct. In my implementation, I have a pointer called `head` that stores the value of the head of the list. If you have `this` as the head of the list, you'll have to deal with that as a special case and copy the data (and `next` pointer) from the node you want to assign to the head, and then delete that node. — David Choweller, Feb 03 '17 at 21:35

Why doesn't this swap adjacent pairs of a LinkedList?

2 Answers2