Exchange nodes in one linked list

Question

I am trying to create a swapNode function that can take any two nodes and replace them. I have developed an algorithm that works if it is at least 2 knots apart, but I cannot come up with an algorithm that will work if they are closer to each other.

Here is what I have written so far:

 void swapNode(call * &head, call * &first, call * &second){ call * firstPrev = NULL; call * secPrev = NULL; call * current = head; //set previous for first while((current->next != first) ){ current = current->next; } firstPrev = current; current = head; //set previous for second while((current->next != second) ){ current = current->next; } secPrev = current; current = second->next; //set firstPrev-> next to second firstPrev->next = second; //set secPrev->next to first secPrev->next = first; //set second->next = first->next second->next = first->next; //set first->next to current first->next = current; current = head; while(current->next != NULL){ cout << current->number << endl; current = current->next; } cout << current->number << endl; } 

EDIT: I now have it as my swap part, but it still doesn't work correctly

 //swap firstPrev-> next with second->next tmp = firstPrev->next; second->next = firstPrev->next; second->next = tmp; //swap swap first->next with second->next tmp = first->next; second->next = first->next; second->next = tmp; 

EDIT2: This one doesn't seem to work either, I get a seg error.

  //swap previous's->next tmp =firstPrev->next; secPrev->next = firstPrev->next; secPrev->next = tmp; //swap swap first->next with second->next tmp = first->next; second->next = first->next; second->next = tmp; 

Answer 1

Let's say that we have:

 Node1 -> Node2 -> Node3 -> Node4 -> Node5 

To swap two nodes, you need to swap next values ​​for them before each of them, as well as next values ​​for the nodes you want to swap.

So, to swap, say, Node2 and Node3, you really need to swap Node1->next to Node2->next and Node2->next to Node3->next . This will work even if they are next to each other (or even if it is the same node). For example:

Swap Node1->next and Node2->next

 Node1->next = Node3 Node2->next = Node2 

Change Node2->next to Node3->next

 Node2->next = Node4 Node3->next = Node2 

It looks like:

 Node1 -> Node3 -> Node2 -> Node4 -> Node5 

Upside down!

As you can see from the comments section, if you change Node1 to anything, you will need to set a new title for the linked list.

---

In response to editing the question:

Your exchange code is almost right. However, you need to change firstPrev to secPrev. In my example, it so happened that we changed one of the values ​​of node next twice, because they were next to each other. But logically, we want to swap the next two of the previous ones, and then swap the next actual nodes. Try the following:

 //swap firstPrev-> next with secPrev->next tmp = firstPrev->next; secPrev->next = firstPrev->next; secPrev->next = tmp; //swap swap first->next with second->next tmp = first->next; second->next = first->next; second->next = tmp; 

If you get segfault, check the tmp variable - it could be a highlight or delete error somewhere. Where do you get segfault?

Answer 2

In most real-life scenarios, the best solution is to replace the values:

 void swapNode(call * &head, call * &first, call * &second) { // swap values, assuming the payload is an int: int tempValue = first->value; first->value = second->value; second->value = tempValue; } 

If this is not allowed, then you want to make a change of a similar style in → next instead of the component → value. And then do another exchange on firstPrev-> next and secondPrev-> next components. Watch for a special case when the first or second == head.

Answer 3

You will also have to swap the next component of the previous node, otherwise the linked list will not stay connected together. Please note that my structure is called node .

 int swapNode( node *&head * &first, node * &second) { //first we will declare the //previous of the swapping nodes node *firstprev=NULL; node*secprev=NULL; node*current=head; //set previous first while(current->next!=first) { current=current->next; } firstprev=current; //seting 2nd previous while(current->next!=second) { current=current->next; } // swap values, assuming the payload is an int: int tempValue = first->value; first->value = second->value; second->value = tempValue; //swaping next of the nodes firstprev->next=second; secprev->next=first; return; } 

Answer 4

Rule of thumb: "Always separate data from pointers and never change pointers, only data!". Make the exchange explicit without using memcpy (), so you can avoid alignment problems. This does not lead to performance degradation in terms of algorithmic complexity, but makes your code more readable and safe.

Answer 5

Here p1 is the first node to be replaced, p2 is the second node to be replaced. And prevnode is the node that precedes p2

  temp=head; while(temp!=NULL){ if(temp->link==p1){ temp->link=p2; prevnode->link=p2->link; p2->link=p1->link; t=p1->link; while(t!=prevnode) t=t->link; cout<<" YES"; cout<<"["<<t->num<<"] "; p1->link=prevnode->link; prevnode->link=p1; temp=p1; }//if_ cout<<" "<<temp->num; temp=temp->link; } 

Answer 6

Although I'm not 100% sure, the answer should include references to the node pointer (or pointers to pointers), and then this should handle the case where one of the nodes is also a list header.

 void swapNodes(node *&first, node *&second) { node *t = second->next; second->next = first->next; first->next = t; t = second; second = first; first = t; } 

Then you can call it, for example:

 swapNodes(head, secPrev->next); 

or

 swapNodes(firstPrev->next, head); 

or

 swapNodes(firstPrev->next, secPrev->next) 

and it should work automatically.

EDIT:

swapNodes can be even more readable:

 void swapNodes(node *&first, node *&second) { std::swap(first->next, second->next); std::swap(first, second); } 

Answer 7

If you want to know all the methods for exchanging two nodes in linked lists in simple C, follow this link:

http://sahilalipuria.wordpress.com/2013/01/21/swapping-two-nodes-of-a-singly-linked-lists-set-2/

Answer 8

 void swap() { struct node *temp=0,*nxt,*ptr; ptr=head; int count=0; while(ptr) { nxt=ptr->link; if(nxt) { if(count==0) head=nxt; count++; ptr->link=nxt->link; nxt->link=ptr; if(temp!=NULL) temp->link=nxt; temp=ptr; if(ptr->link==NULL) break; ptr=nxt->link->link; } 

}}

Answer 9

Thank you all for your answers! I really understand that this question was asked almost two years ago, and the answer has long been accepted, but I was a little confused by the answers. Thus, although the questionnaire probably does not care about the new answers, I would like to add my version if other readers are confused and document my own approach. Some of them may have been more suitable as comments, but I do not yet have a reputation for comment.

Firstly, no matter how often I look at it - on the board or in the debugger - I cannot avoid ending the loop in the first node, that is, pointing to myself, if I do not use to conditionally distinguish between cases of mixing nodes, and not even with abstract steps or specific code from Smashery's currently accepted answer. I searched the Internet a bit to find the code in the style of the currently accepted answer in order to avoid such a conditional, but for me it is surprisingly difficult to avoid, and my searches did not find such a solution (if I am not mistaken about the proposed, possibly incorrect). If there was some kind of clever expression that would give the first node address when they are adjacent, and the first node prefix when they are not, this condition is not needed, because the second new node successor is found out which (apparently) requires conditional.

Secondly, I have the same question about successive assignments to the same variables in the accepted answer as other commentators. I hope I'm not very dense here, but assigning different values ​​to the same variable in the sequence, unless, perhaps, in case of side effects, it just never seems to me that she left the variable with any other value than the last assignment, regardless on what configuration of nodes I am considering, and thus makes previous assignments clearly redundant. If I am wrong about this, and this approach will actually solve this problem, then I could eliminate the last condition in the code below, which I tried to get rid of when I first saw the solution on the Internet for replacing nodes without adjacent nodes of a special casing string. I'm not quite sure, but it sounded like Smashery deliberately left these repetitive tasks out of logical rigor and better illustrated the procedure — I might have misunderstood.

Thirdly, on this and other sites I often saw that the assertion from other answers repeated that it is better to exchange the contents of nodes, rather than pointers. Of course, in the case of prime integers, as in the examples above, this apparently gives a shorter, simpler code. However, when we discuss linked lists with nodes containing integers, it is usually a backup for the backup data structure of a more complex and universal container. Thus, I do not think that replacing the contents of nodes is actually so simple, at least if the implementation of the data structure cannot make assumptions about the semantics of the instance of the container elements. In addition, the ability to exchange the contents of nodes like me implies that the linked list has the right to own the contents of these nodes, because otherwise the code outside the linked list method may contain links to objects in these nodes whose values ​​suddenly change under them.

I acknowledge, however, that this may depend on the semantics of the container. For an array, you can expect the swap method to change the value under links to a specific index of that array. This means that the links are not intended to indicate a specific object, but rather for a position in a container that can be indexed. If we consider the linked list as a means only to order a set of objects that use them outside of the linked list, the user probably expects the swap operation to replace only the position, not the content.

Imagine, for example, that a linked list represents objects of the type “car”. Each car has an owner, and this owner refers to his car through a pointer to it. Now suppose that the linked list is an order for a set of cars that must be serviced for inspection at a car dealership. If we change the contents of two nodes to exchange slots for two cars and do this by exchanging their contents, then the service will really happen in the new correct order - but people will also end up with different cars! (I would not want to swap places with Tesla, because I just drove Corolla.)

If the linked list was, as in the array example, based on indexing semantics, then the position in the node can simply represent the order in which the cars are loaded onto the ship for transportation. At the moment, the cars have no owners, and we really only care about which slot they are in. Then, I believe, it really doesn’t hurt to change cars, that is, to the contents of the objects referenced by the nodes.

Finally, to the code. As I said above, I could not avoid a special shell for neighboring nodes.

First, the definition of a helper method:

 int find_node(int v, node* root, node** n, node** pn) { int i = 0; for (*n = root; *n != NULL && (*n)->v != v; ++i) { *pn = *n; *n = (*n)->next; } return i; } 

This method finds node by its value. The returned integer is a position based on a zero value (call it the index, if you want) node in the linked list. I found that position adjacency detection, not pointer comparison, is more readable. The beginning of the list is root. The method sets n to point to the node containing the passed value. In pn, the method stores the predecessor of n.

The following is the actual swap:

 void swap_nodes(node **root, int v1, int v2) { if (v1 == v2) return; node *n1, *n2, *pn1, *pn2; int p1 = find_node(v1, *root, &n1, &pn1); int p2 = find_node(v2, *root, &n2, &pn2); if (p1 > p2) { std::swap(n1, n2); std::swap(pn1, pn2); std::swap(p1, p2); } if (p1 == 0) *root = n2; else pn1->next = n2; node* nn1 = n1->next; n1->next = n2->next; if (p2 - p1 > 1) { n2->next = nn1; pn2->next = n1; } else { n2->next = n1; } } 

Sorry, I changed the OP method signatures a bit. I found it more convenient to pass the values ​​of nodes for exchange, as opposed to node pointers. If you pass the node pointers only to the corresponding nodes, you will have to do another workaround to find the predecessors with this solution, which was a bit inconvenient for me. If we cannot distinguish nodes by these values, for example. values ​​are not unique, we need pointers to nodes.

As with the description of find_node above, we first find the positions, nodes, and predecessors for the node values ​​passed to swap_nodes via v1 and v2. The values ​​for the first and second nodes are replaced if the second node replacement appears before the first. This is not much code for this, it reduces the special case and makes it a little easier to visualize.

Now we have only two conditional expressions left, none of which seemed trivial. If the first node is at the head of the linked list, that is, at the zero position, the root node must point to the second node. Otherwise, the first predecessor node will point to the second node.

The previous value of the first successor node must be remembered if the nodes are not adjacent. Then the first successor node is installed on the current successor of the second node. This is the only change that applies to all cases: the new successor of the first node, which is the old successor of the second node, is the only certainty and useful to start with, to remember the pointer operations and their sequence when implementing this swap.

Finally, if the positions of the nodes differ by more than one, they are not adjacent. Then the second node successor becomes the first old node successor - saved above - and the second node predecessor now points to the first node. If they are adjacent, there are no nodes between nodes that require updating, so just binding the second node to the first is all that remains to be done.