Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Given a linked list and its two keys, swap the two nodes of the given key. Nodes should be swapped by changing links. When the data contains many fields, it can be expensive to swap the data for nodes in many cases.

You can assume that all keys in a linked list are different.

Example:

Input:10->15->12->13->20->14, x =12, y =20Output:10->15->20->13->12->14Input:10->15->12->13->20->14, x =10, y =20Output:20->15->12->13->10->14Input:10->15->12->13->20->14, x =12, y =13Output:10->15->13->12->20->14
Copy the code

This may seem like a simple question, but it’s an interesting one because it has the following situations to deal with.

  1. X and y may or may not be adjacent.
  2. Either x or y can be a head node.
  3. X or y could be the last node.
  4. X and/or y may not exist in a linked list.

How to write clean working code that handles all of the above possibilities.

The idea is to first search for x and y in a given linked list. If any of them do not exist, return. Tracks current and previous Pointers when searching for x and y. First change the next of the previous pointer, and then change the next of the current pointer.

The following is an implementation of the above method.


class Node {
public:
	int data;
	Node* next;
};

void swapNodes(Node** head_ref, int x, int y)
{
	if (x == y)
		return;

	Node *prevX = NULL, *currX = *head_ref;
	while(currX && currX->data ! = x) { prevX = currX; currX = currX->next; } Node *prevY =NULL, *currY = *head_ref;
	while(currY && currY->data ! = y) { prevY = currY; currY = currY->next; }if (currX == NULL || currY == NULL)
		return;

	if(prevX ! =NULL)
		prevX->next = currY;
	else 
		*head_ref = currY;

	if(prevY ! =NULL)
		prevY->next = currX;
	else 
		*head_ref = currX;

	Node* temp = currY->next;
	currY->next = currX->next;
	currX->next = temp;
}

void push(Node** head_ref, int new_data)
{
	Node* new_node = new Node(a); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; }void printList(Node* node)
{
	while(node ! =NULL) {
		cout << node->data << ""; node = node->next; }}int main(a)
{
	Node* start = NULL;

	push(&start, 7);
	push(&start, 6);
	push(&start, 5);
	push(&start, 4);
	push(&start, 3);
	push(&start, 2);
	push(&start, 1);

	cout << "Linked list before calling swapNodes() ";
	printList(start);

	swapNodes(&start, 4.3);

	cout << "\nLinked list after calling swapNodes() ";
	printList(start);

	return 0;
}
Copy the code

Optimization: The above code can be optimized to search for x and y in a single walk. Two loops are used to keep the program simple.

The easier way to do it

#include <iostream>

using namespace std;

class Node {

public:
	int data;
	class Node* next;

	Node(int val, Node* next)
		: data(val)
		, next(next)
	{
	}

	void printList(a)
	{

		Node* node = this;

		while(node ! =NULL) {

			cout << node->data << ""; node = node->next; } cout << endl; }};void push(Node** head_ref, int new_data)
{

	(*head_ref) = new Node(new_data, *head_ref);
}

void swap(Node*& a, Node*& b)
{

	Node* temp = a;
	a = b;
	b = temp;
}

void swapNodes(Node** head_ref, int x, int y)
{

	if (x == y)
		return;

	Node **a = NULL, **b = NULL;

	while (*head_ref) {

		if ((*head_ref)->data == x) {
			a = head_ref;
		}

		else if ((*head_ref)->data == y) {
			b = head_ref;
		}

		head_ref = &((*head_ref)->next);
	}

	if (a && b) {

		swap(*a, *b);
		swap(((*a)->next), ((*b)->next)); }}int main(a)
{

	Node* start = NULL;

	push(&start, 7);
	push(&start, 6);
	push(&start, 5);
	push(&start, 4);
	push(&start, 3);
	push(&start, 2);
	push(&start, 1);

	cout << "Linked list before calling swapNodes() ";
	start->printList(a);swapNodes(&start, 6.1);

	cout << "Linked list after calling swapNodes() ";
	start->printList(a); }Copy the code

The output

Linked list before calling swapNodes(a) 1 2 3 4 5 6 7 
Linked list after calling swapNodes(a)6, 2, 3, 4, 5, 1, 7Copy the code

🥇 past quality articles

Teach you make a small game gobang in Java Single AI minesweeping game using the python list of singly linked list data structure is introduced | first set of singly linked list data structure in the linked list and array | second singly linked list data structure of chain table insert | | delete nodes of the third set of singly linked list data structure in the fourth set Singly linked list data structure to delete a given location of a linked list node | the fifth set of the view of singly linked list data structure arrays and linked list method | singly linked list data structure of the set of 6-1 check method of array and list | set 6-2

📣 Endnote: For more information on data structures, you can follow me: Haiyong, I hope you found this article helpful.

If you see this, thank you for reading 🙂

💌 welcomes your comments and suggestions in the comments section! 💌

If you really learn something new from this article, like it, bookmark it and share it with your friends. 🤗 and finally, don’t forget ❤ or 📑.