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 you are given a linked list:

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

Expected Result:

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

Every 2 alternative links should be replaced.

I wrote a solution here. Can you offer me another solution. Can you comment on my decision and help me write it better?

 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 the members "Next" and "Data":

  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 replace it with the data of the following (one). Plain.

Edit: above the solution swaps the data in the nodes, but not the nodes themselves. If you want to exchange the actual nodes, the solution requires more logic.

Answer 2

Take a look at this solution in C ++:

 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, the current is the head of the node.

Answer 3

@dkamins: U changes the meaning, but in these types of questions, interviewers are usually asked to shuffle the pointer.

My problem attempt:

 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 4

Here it is in full runnable Java. This is a pure pointer game.

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

Answer 5

I adapted the @dkamins solution, in some way. Instead of pointing to a pointer, I return a new head . I also strengthened this.

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

In principle, the new list title is either the current head, if NULL , or the length is 1, or the second element.

In the swap cycle, tmp will eventually become the second element, but first it is the first. Therefore, we need to point to the 3rd element, which is the target of tmp->next = n->next; . I do not use a for loop, because if we did this, it would be less intuitive - the revaluation expression would only seem to jump 1 node per iteration. At the end of the loop while n = tmp->next; makes intuitive sense - we point it to the element after tmp , the second element.

The most important part is the last line. Since we are doing this in the forward direction, we must remember that the previous second iteration element will almost certainly point to the current iteration element 4th , because this iteration will replace 3 and 4 So, at the end of the iteration, if we understand that we will again change the next iteration, we calmly point the 2nd element to the current 4th element, knowing that the next iteration will be the 3rd element, and everything is true in the world.

For example, if list 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 normal because n = 3, so we have not lost that node. Next iteration:

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

Answering the final answer 7 -> 2 -> 5 -> 3 .

Answer 6

I think in order to make it more efficient, it would be better to take another argument n in the function. This n is used for counting, that is, after how many counting nodes need to be changed. in the above case, n = 2. And then continue the iteration until you press n and use the alternative link list or alternative reverse link list for links.

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

}

Answer 7

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

It works!?
Because.
let's say:

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

After the cycle

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

and then.

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

Is this what we expect right?
But you know. The real thing will be.

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

Because u did not change 1-> the following link to 4! He still points to 3!
My version: Click here

Answer 8

here is my C ++ code: it will return a pointer to a linked list with replacement

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

Answer 9

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

Answer 10

Here "head" is a pointer to the first node of the linked list, and the function returns a 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; 

}

Answer 11

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

Answer 12

Here is my C function for exchanging alternate node links in a linked list. I have included comments in the code. For a better understanding, take an example and follow the steps by making diagrams using a 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 } } 

Answer 13

My decision: -

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

Answer 14

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

Answer 15

This may 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-> 

Answer 16

C Swap Code Related

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