CODEWITHSUNDEEP
java
OneMoreError
OneMoreError

Reputation: 7728

Java Reverse a linked list pairwise

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.

Upvotes: 2

Views: 850

Answers (2)

sol4me
sol4me

Reputation: 15698

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

Upvotes: 1

Giovanni Botta
Giovanni Botta

Reputation: 9816

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).

Upvotes: 1

Related Questions