Swap nodes in a singly-linked list

I am trying to swap two nodes. For example if the nodes are a and b I am passing the pointers
(a-1)->next and (b-1)->next which are basically nodes a and b.

void swap(struct stack **a,struct stack **b)
{
    struct stack *temp1 = *a, *temp2 = *b, *temp3 = *b;      
    *a = *b; 
    (*b)->next = (temp1)->next;
    temp2 = temp1;
    (temp2)->next = temp3->next;
}

What am I doing wrong? When I am trying to print the nodes after calling the function it's an infinite loop. Please help.

回答1:

Why Infinite loop?

Infinite loop is because of self loop in your list after calling swap() function. In swap() code following statement is buggy.

(*b)->next = (temp1)->next;

Why?: Because after the assignment statement in swap() function temp1's next starts pointing to b node. And node[b]'s next point to itself in a loop. And the self loop is reason for infinite loop, somewhere in your code where you traverse linked list.

Below I drawn to show how swap() works step-by-step. May be this help you to understand your error:

You didn't mention but I am assuming linked list having following relation between a and b: (read red comments)

(step-1):

+----+----+----+      +---+----+----+
|      one     |----->|    two      |
+----+----+----+      +---+---+-----+
  ^     ^              ^    ^
  |     |              |    |
  |    *a              |   *b
  |                    | 
 temp1                temp2, temp3     "after assignment to temp variables"

(step-2):                   ^
                            | 
*a = *b                     | *a       "<--- next step"

(step-3): The buggy statement

(*b)->next = (temp1)->next;          "Change link: (temp1)->next; is `two` node"
                                     " *b is `two`,   So Self loop" 


+----+----+----+      +---+----+----+ <---|  
|      one     |      |    two      |-----|
+----+----+----+      +---+---+-----+
  ^                    ^    ^    ^
  |                    |    |    |
  |                    |   *b    *a
  |                    | 
 temp1                temp2, temp3    "  after assignment to temp"

See (temp1)->next; is actually b and you are assigning (*b)->next = (*b) by doing (*b)->next = (temp1)->next; hence adding a self loop.

(step-4):
I think with the diagram you can easily understand what last two lines of your swap() code are doing:

temp2 = temp1;
(temp2)->next = temp3->next;

Following is my diagram for this two lines:

temp2 = temp1;         
+----+----+----+      +---+----+----+ <---|
|      one     |      |    two      |-----|  "<--- Self loop"
+----+----+----+      +---+---+-----+
  ^                    ^    ^    ^
  |                    |    |    |
  |                    |   *b    *a
  |                    | 
  temp2 = temp1;      temp3

(step-5): Even last line of your function swap() left loop as below:

 (temp2)->next = temp3->next;  " last line of your code"

+----+----+----+      +---+----+----+ <---|
|      one     |----->|    two      |-----|  "<-- Self loop"
+----+----+----+      +---+---+-----+
  ^                    ^    ^    ^
  |                    |    |    |
  |                    |   *b    *a
  |                    | 
temp2 = temp1;          temp3

So loop still there at two node so infinite loop.

How to swap two nodes in single linked list?

One way is swap node's data instead of swapping node's position it self in linked list (as I commented to your question). But you wants to swap node's position in list.
Well this good! if node data size is larger, that time its better to swap node's position rather then swap node's data(swapping data will be bad choice)

Because you having single linked list, to swap any two arbitrary nodes in list you need there previous node addresses too. (this is the point you don't consider in your swapping logic)

WHY need previous pointers?:
Suppose after some successful insert(push) operations, your list becomes as follows:

 0  <--------TOP - "head"
 9  <--p  
 2    
 6  <--q           
 5

A horizontal diagram- Suppose you want to swap say two nodes (q) and (p):

+---+    +---+    +---+    +---+    +---+                               
| 0 |--->| 9 |--->| 2 |--->| 6 |--->| 5 |---
+---+    +---+    +---+    +---+    +---+  |                                
 ^        ^                  ^            null  
 |        |                  | 
 |       (q)                (p)   
 (head)

As I said, to swap we need previous pointers. You need to think about following
(In theory, I am writing for specific nodes (p) and (q) just to keep explanation simple. but my implementation is quit general):

In list previous pointers:

node[0] points to node[9] that is (q), and 
node[2] points to node[6] that is (p)

And

node[9] points to node[2]
node[6] points to node[5]

NOTICE: If you want to swap two nodes say node[ 9 ] and node[ 6 ] then you should use pointers of the nodes previous to these two nodes.
For example: two swap node[ 9 ] and [ 6 ], you also need to change next pointer of node[ 0 ] and next pointer of node[ 2 ] in above diagram.

How would be the list after swapping this two nodes?

+---+    +---+    +---+    +---+    +---+                               
| 0 |--->| 6 |--->| 2 |--->| 9 |--->| 5 |---
+---+    +---+    +---+    +---+    +---+  |                                
 ^        ^                  ^            null  
 |        |                  | 
 |       (p)                (q)   
 (head)

What is now in previous nodes [o] and [2]?
After swapping, In list previous pointers

node[0] points to node[6] that is (q), and 
node[2] points to node[9] that is (p)

And

node[9] points to node[5]
node[6] points to node[2]

So if you want to swap two nodes; there immediate previous node also effects and because list is single link list you need previous pointers too.

How to find previous node pointers?

Suppose you want to swap any two nodes node[p] and node[q] then you can use head pointer to find previous node.

So swap function syntax (In my implementation) is like:

void swap(struct stack **head, // head node 
          struct stack **a,    // first candidate node to swap
          struct stack **b);   // first candidate node to swap

And you will call function like:

swap(&head, &p, &q);

Definition: (To understand code please read comments I added at almost each line)

void swap(struct stack **head, 
          struct stack **a, 
          struct stack **b){
  // first check if a agrgument is null                 
  if( (*head) == NULL ||               // Empty list         
        (*a) == NULL || (*b) == NULL){     // one node is null  
       // Nothing to swap, just return 
        printf("\n Nothing to swap, just return \n");
        return;
  }     

  // find previos nodes
  struct stack* pre_a = get_prevnd(*head, *a);
  struct stack* pre_b = get_prevnd(*head, *b);

  //Now swap previous node's next
  if(pre_a) pre_a->next = (*b); // a's previous become b's previous, and 
  if(pre_b) pre_b->next = (*a); // b's previous become a's previous

  //Now swap next fiels of candidate nodes  
  struct stack* temp = NULL;  
    temp = (*a)->next;
  (*a)->next = (*b)->next;
  (*b)->next = temp;

  //change head: if any node was a head 
  if((*head)==(*a)) 
     *head = *b;
  else 
     if((*head)==(*b))  
        *head = *a;
}

In swap() function you can notice that I call a helper function get_prevnd(, );. This function returns address of previous node in list. In The function get_prevnd(, );, first argument is list head and second argument is node for which you are looking for.

// find previous node function()
struct stack* get_prevnd(
                 struct stack* head, 
                 struct stack* a
                ){
    if(head == a){
        // node[a] is first node 
        return NULL;
    }
    struct stack* temp = head; // temp is current node
    struct stack* pre_a = NULL; 

    while(temp && temp!=a){ //search while not reach to end or the node
        pre_a = temp;          // find previous node   
        temp = temp->next;
    }
    if(temp!=a){// node[a] not present in list
        fprintf(stderr, "\n error: node not found!\n");
        exit(EXIT_FAILURE); // bad technique to exit()
    }
    return pre_a;   
}

And fortunately the code is WORKING :). Below is link for online test of this code. I have tested for various kind of inputs.

CodePad: To Swap node in single linked list. Please check output.

_{And sorry for bad English}

回答2:

I was hoping for cut-and-paste code, but didn't find it. If anyone is still interested, this is the answer. I did the brute force analysis of all 3 cases.

// swaps nodes at locations *sp and *tp
struct stack *s = *sp; // store locations to prevent overwritten bugs
struct stack *t = *tp;
if(&t->next == sp) { // order u (tp)-> t (sp)-> s -> ...
    t->next = s->next;
    s->next = t;
    *tp = s;
} else if(&s->next == tp) { // order u (sp)-> s (tp)-> t -> ...
    s->next = t->next;
    t->next = s;
    *sp = t;
} else { // disconnected u (sp)->s -> ..., v (tp)->t -> ...
    struct stack *next = s->next;
    s->next = t->next;
    t->next = next;
    *sp = t;
    *tp = s;
}             
// If you track the end of your list, it be the one pointing to NULL.                                           
if(s->next == NULL) {                                  
    end = &s->next;                                 
} else if(t->next == NULL) {                           
    end = &t->next;                                 
}

Note: This code works if sp == tp, but assumes you don't have the pathological case where BOTH &s->next == tp && &t->next == sp (starting with cycle).

回答3:

        "KING KHAN"

SwapanyTwoNodeData(int, int); this function take two integer as parameter and swap these

node data.

1->2->6->3->4->5

SwapanyTwoNodeData (2,4);

1->3->6->2->4->5

100% Working Function. . . . Enjoy.

void Swap_Any_Two_Locations_data(int x,int x1){

   if(head!=NULL){     
     int count=1,count1=1;     
     Node *temp,*temp1;
     temp=head;
     temp1=head;
     while(temp->next!=NULL && count!=x ){
         temp=temp->next;
         count++;
     }
     while(temp1->next!=NULL && count1!=x1){
         temp1=temp1->next;
         count1++;
     }
     if(count==x && count1==x1){
       int z=0;
       z=temp->info;
       temp->info=temp1->info;
       temp1->info=z;
       cout<<"Data Swapped"<<endl;
    }
  }
}