Java Reverse a linked list pairwise

Question

I am trying to reverse a linked list pairwise i.e as follows

1->2->3->4->5 changed to 2->1->4->3->5

I have been able to do that recursively. However, I am getting confused while doing it iteratively.

public class FastList<Item>
{
    private Node<Item> first;

    private static class Node<Item>
    {
        Item item;  
        Node<Item> next;
    }

    public void swapPairwiseIterative()  // not working
    {
        if(first == null || first.next==null)
            return;

        Node one = first, two;
        first= first.next;

        while ( one != null || one.next != null )
        {
            two = one.next;
            one.next = two.next;
            two.next = one;
            one = one.next.next;
        }
    }
}

On debugging, I noticed that I am able to swap the two nodes correctly, but am not able to assign it back to the first instance variable, which points to the first element of the list. How do I do that ?

Also, the line

first= first.next;

looks a bit hacky. Please suggest a more natural way of doing it.

since I hate to answer people's homeworks with code. just store the pairs. and have a link to the parent for speed. Otherwise every iteration is an average of n/2 acceses. — Andrew Scott Evans
– Andrew Scott Evans, Commented Dec 5, 2014 at 19:02
Say I am processing the pair 3->4, how do I change 2 to point to 4 and not 3 given it is a singly linked list. — OneMoreError
– OneMoreError, Commented Dec 5, 2014 at 19:04
Shouldn't one = one.next.next be one = one.next? since you are swaping one and two, one takes the position of two thus making the start of the next pair be the first node after one, not second — nem035
– nem035, Commented Dec 5, 2014 at 19:05

Giovanni Botta · Accepted Answer · 2014-12-05 19:13:52Z

1

Try something like this:

public void swapPairwiseIteratively() {
  if(first == null || first.next==null) return;
  Node one = first, two = first.next, prev = null;
  first = two;
  while (one != null && two != null) {
    // the previous node should point to two
    if (prev != null) prev.next = two;
    // node one should point to the one after two
    one.next = two.next;
    // node two should point to one
    two.next = one;
    // getting ready for next iteration
    // one (now the last node) is the prev node
    prev = one;
    // one is prev's successor
    one = prev.next;
    // two is prev's successor's successor
    if (prev.next != null) two = prev.next.next;
    else two = null;
  }
}

I am not sure you can do it with only two pointers instead of three. I would work from the solution above (I haven't tested it but it should be correct) and figure out if it can be improved. I don't think the line first = two can be removed.

You could remove the condition if (prev != null) if you move the first pair swapping out of the loop (an optimization that is premature in this example).

edited Dec 5, 2014 at 19:13

answered Dec 5, 2014 at 19:05

Giovanni Botta

9,8366 gold badges55 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Kick Buttowski Over a year ago

@OneMoreError if it helped, at least accept the answer

sol4me · Accepted Answer · 2014-12-05 19:25:47Z

1

You can do it either recursively or non-recursively.

public void reverseRecursive(Node startNode)
{
    Item tmp;
    if(startNode==null || startNode.next ==null)
        return;
    else
    {

        tmp =  startNode.item;
        startNode.item = startNode.next.item;
        startNode.next.item = tmp;

        reverseRecursive(startNode.next.next);
    }

}

Non Recursively

public void reverseNonRecursive()
{
    Node startNode = head;
    Item temp;

    while(startNode != null && startNode.next != null)
    {
        temp =  startNode.item;
        startNode.item = startNode.next.item;
        startNode.next.item= temp;
        startNode = startNode.next.next;
    }
}

answered Dec 5, 2014 at 19:25

sol4me

15.8k6 gold badges37 silver badges35 bronze badges

1 Comment

Gene Over a year ago

His code is swapping pointers. I don't think swapping intrinsic data is what he wants.

Collectives™ on Stack Overflow

Java Reverse a linked list pairwise

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related