Given a linked list of numbers. Swap every 2 adjacent links.

Question

Given a linked list of numbers. Swap every 2 adjacent links. For example, if a linked list given to you is:

a->b->c->d->e->f 

Output expected:

b->a->d->c->f->e

Every 2 alternate links have to be swapped.

I have written a solution here. Can you suggest me some other solution. Can you comment on my solution and help me better write it?

void SwapAdjacentNodes (Node head)
{
    if (head == null) return; 

    if (head.next == null) return; 
    Node curr = head;
    Node next = curr.Next;
    Node temp = next.Next;

    while (true)
    {
        temp = next.Next;
        next.Next = curr;
        curr.Next = temp;

        if  (curr.Next != null)
            curr = curr.Next;
        else
            break;
        if (curr.Next.Next!=null)
            next = curr.Next.Next;
        else
            break;
    }   
}

Answer 1

Here's a rough sketch of a much simpler version, assuming Node has "Next" and "Data" members:

  for (Node n = head; n && n.Next; n = n.Next.Next) {
    void* tmp = n.Data;
    n.Data = n.Next.Data;
    n.Next.Data = tmp;
  }

In other words, stop at every other node in the list and swap its data with the next one (the one). Simple.

Answer 2

@dkamins: U are changing the values but in these type of questions, interviewers generally ask for pointer shuffling.

My attempt for the problem:

void swap (struct list **list1)
{
    struct list *cur, *tmp, *next;
    cur = *list1;

    if(!cur || !cur->next)
              return;

    *list1 = cur->next;

    while(cur && cur->next)
    {
              next = cur->next;
              cur->next = next->next;
              tmp = cur->next;
              next->next = cur;
              if(tmp && tmp->next)
                  cur->next = cur->next->next;
              cur = tmp;                                  
    }
}

Answer 3

Here it is in complete runnable Java. This is purely pointer play.

public class ListSwap {
    // the swap algorithm
    static void swap(Node current) {
        while (true) {
            Node next1 = current.next;
            if (next1 == null) break;
            Node next2 = next1.next;
            if (next2 == null) break;
            Node next3 = next2.next;
            current.next = next2;
            next2.next = next1;
            next1.next = next3;
            current = next1;
        }
    }
    // the rest is infrastructure for testing
    static class Node {
        Node next;
        final char data; // final! Only pointer play allowed!
        Node(char data, Node next) {
            this.data = data;
            this.next = next;
        }
        @Override public String toString() {
            return data + (next != null ? next.toString() : "");
        }
    }

(continued...)

    static class List {
        Node head;
        List(String data) {
            head = null;
            String dataReversed = new StringBuilder(data).reverse().toString();
            for (char ch : dataReversed.toCharArray()) {
                head = new Node(ch, head);
            }
            head = new Node('@', head);
        }
        @Override public String toString() {
            return head.toString();
        }
        void swapPairs() {
            swap(head);
        }
    }
    public static void main(String[] args) {
        String data = "a1b2c3d4e5";
        for (int L = 0; L <= data.length(); L++) {
            List list = new List(data.substring(0, L));
            System.out.println(list);
            list.swapPairs();
            System.out.println(list);
        }
    }
}

(see full output)

Answer 4

I adapted @dkamins' solution, in a way. Instead of taking in a pointer to a pointer, I return the new head. I also beefed it up.

struct Node
{
   struct Node *next;
   int data;
};

typedef struct Node * NodePtr;
NodePtr swapEveryTwo(NodePtr head)
{
   NodePtr newHead = (head && head->next) ? head->next : head;
   NodePtr n = head;
   while(n && n->next)
   {
      NodePtr tmp = n;     // save (1)
      n = n->next;         // (1) = (2)
      tmp->next = n->next; // point to the 3rd item
      n->next = tmp;       // (2) = saved (1)
      n = tmp->next;       // move to item 3

      // important if there will be further swaps
      if(n && n->next) tmp->next = n->next;
   }

   // return the new head
   return newHead;
}

Basically, the new head of the list is either the current head if NULL or length 1, or the 2nd element.

In the swap loop, tmp will eventually become the 2nd element, but initially it is the first. We need it therefore to point to the 3rd element, which is the purpose of tmp->next = n->next;. I don't use a for loop because if we did, it is less intuitive - the reevaluation expression would only appear to be jumping by 1 node per iteration. At the end of the while loop, n = tmp->next; makes intuitive sense - we are pointing it to the element after tmp, the 2nd element.

The most important part is the last line. Because we are doing this in a forward direction, we have to remember that the previous iteration's 2nd element is almost certainly going to be pointing to the current iteration's eventual 4th element, because this iteration will swap 3 and 4. So at the end of the iteration, if we realize we are going to swap again next iteration, we quietly point the 2nd element to the current 4th element, knowing that next iteration it will be the 3rd element and all is right in the world.

For example, if the list is 2 -> 7 -> 3 -> 5:

n = 2
tmp = 2
n = 7
tmp->next = 3 (2 -> 3)
n->next = 2 (7 -> 2)
n = 3
7 -> 2 -> 3 -> 5

but then there will be swaps, so the last statement says
7 -> 2 -> 5      3?

This is ok because n = 3, so we haven't lost that node. Next iteration:

n = 3
tmp = 3
n = 5
tmp->next = NULL (3 -> NULL)
n->next = 3  (5 -> 3)
n = NULL

Leading to the final 7 -> 2 -> 5 -> 3 answer.