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

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
开发者_JS百科

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

Take a look at this C++ solution:

public void exchangeAdjElements(){
    LLMain backup=current.next;
    LLMain temp = current.next;
    LLMain previous=current;
    while(current!=null && current.next!=null){
        previous.next=current.next;
        current.next=temp.next;
        temp.next=current;
        if(current.next!=null){
            previous=current;
            current=current.next;
            temp=current.next;
        }
    }
    current=backup;
}

Here current is the head node.

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.

Edit: Above solution swaps data within the nodes but not the nodes themselves. If you want to swap actual nodes, the solution requires more logic.

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

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)

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.

I guess to make it more efficient, it would be better to take another argument n in the function. This n is used for count , i.e after how much count the nodes needs to be changed. in above case n= 2. And then keep on iterating until you hit the n and used the reverse linklist alog or recursive reverse linklist algo to do it.

void ReverseLinkList(struct node* head, int n) { if( head == null || null <= 0) return;

struct node* start = head;
struct node* next = null;
struct node* end = head;

int count = 1;

while(end->next != null)
{
    if(count == n)
    {
        next = end->next;
        count = 1;
        //Use ReverseLinklist From start to end
        end->next = next;
        end = next;
        start = next;
    }
    else
    {
        end = end->next;
        count++;
    }
}

}

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

Does it work!?
Because.
say :

1[cur] -> 2[next] -> 3 [temp]-> 4

After the loop

2 -> 1 -> 3[cur] -> 4[next] -> NULL [temp]

and then.

2 -> 1 -> 4 -> 3 ->  NULL

That is what we expect right?
But u know. The real thing will be like.

2 -> (1,4) -> 3  -> NULL

Because u didn't change the 1->next link to 4! It still points to 3!
MY VERSION : Click here

here's my c++ code : it will return the pointer to the swapped linked list

Node* swap_list(Node* node) {
if(node == NULL)
    return NULL;

Node* ret = node->next;
Node* pre_a = NULL;
Node* a = node;
Node* b = node->next;   

while(a!=NULL && b!=NULL) {     
    a->next = b->next;
    b->next = a;
    if(pre_a!=NULL)
        pre_a->next = b;
    pre_a = a;
    a = a->next;
    if(a==NULL) break;
    b = a->next;        
}

return ret;
}

private static SList swapAlternateElements(SList n){

    if(n == null)
        return n;
    SList head = swap(n);
    SList tail = head;

    while(tail == null || tail.next != null){
        tail.next.next = swap(tail.next.next);
        tail = tail.next.next;
    }

    return head;

}

private static SList swap(SList n){

    if(n.next == null || n==null){
        return n;
    }
    SList current = n.next;
    SList next = current.next;
    n.next = next;
    current.next = n;
    return current;

}

I tried to solve it and here is the solution.

public Node swapAdjacentNodes() {
    if (head == null)
        return null;
    if (head.nextNode == null)
        return head;
    Node previous = null;
    Node current = head;
    Node next = head.nextNode;
    while (next != null && next != current) {
        current.nextNode = next.nextNode;
        next.nextNode = current;
        if (previous == null) {
            previous = next;
            head = previous;
            previous = previous.nextNode;
        } else {
            previous.nextNode = next;
            previous = previous.nextNode.nextNode;
        }
        current = current.nextNode;
        if (current == null)
            break;
        next = next.nextNode.nextNode.nextNode;

    }
    return head;

}

Here is my C function to swap links of alternate nodes in linked list.I have included comments in the code. For better understanding take an example and run through the steps by making diagrams using pen and paper.

 void swap_alternate_nodes(struct node **head)
    {
        if(*head==NULL)
            return;
        if((*head)->next==NULL)
            return;

        struct node *prev = *head;
        struct node *curr = (*head)->next;
        struct node *temp = NULL;
        *head = (*head)->next; // new head will be second node
        while(curr!=NULL && prev!=NULL)
        {
            if(temp!=NULL)
                temp->next = curr; // previous prev node pointer should point to curr pointer

            prev->next = curr->next; // update prev node pointer

            curr->next = prev; // update curr node pointer

            temp = prev; //store prev pointer

            prev = prev->next; // forward prev pointer

            if(prev)
                curr = prev->next; // forward curr pointer
        }
    }

My take on the solution:-

public Node exchangeAdjacentNodes(Node head){
     Node curr = head;
     Node temp=null,next=null;
     if(curr==null||curr.next==null){
         return curr;
     Node head = curr.next;
     while(curr!=null && curr.next!=null){
           next = curr.next;
           curr.next=next.next;
           temp = curr.next;
           next.next = curr;
           if(temp!=null && temp.next!=null)
                 curr.next = curr.next.next;
           curr=temp;
      }
      return head;
}

Here, 'head' is the pointer to the first node of the Linked-List and the function returns the new head pointer.

node* swapPairs(node *head) {
if(head==NULL || head->next==NULL) {
    return head;
}

node *ptr1=head->next;
node *ptr2=ptr1->next;
ptr1->next=head;
head->next=swapPairs(ptr2);
return ptr1;

}

public void swapAdjacent() {
    temp = head;
    while (temp != null && temp.next != null) {
        Object tem = temp.val;
        temp.val = temp.next.val;
        temp.next.val = (Object) tem;
        temp = temp.next.next;
    }
}

It might help : public static void main(String[] args) {

    String arr[] = { "a", "b", "c", "d", "e", "f" };
    int i = 0;
    int k = 1;
    String temp;

    while (k <= arr.length - 1 && arr[i] != null && arr[k] != null) {

        temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;

        k++;
        i = k;
        k++;
    }
    for (int j = 0; j < arr.length; j++) {

        System.out.print(arr[j]+"->");
    }

}
// Input  ->  a->b->c->d->e->f->
// Output -> b->a->d->c->f->e->

C Code to swap Adjacent

node *SwapAdjacent(node *root)
{
    *NextNode = NULL;
    node * result = root->next;
    node *prev = NULL;
    while (root != NULL && root->next!=NULL)
    {
        if(prev!=NULL)
            prev->next= root->next;
        NextNode = root->next->next;
        root->next->next = root;
        root->next = NextNode;
        prev = root;
        root = NextNode;
    }
    return result;
}