Swapping two adjacent linked lists nodes

I am working on a program where I sort elements into alphabetical order and then when one is less than the other I swap them. I first did it by swapping the data but they want me to swap the nodes instead and I am having trouble doing that. Any help would be appreciated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
Node *add_node( Node *list, const string &s )
{
    struct Node *n = new struct Node;
    n->word = s;            // copy string s to word
    n->next = 0;

	// add node n to the list 
	// the list should always be in ascending alphabetical order
	n->next = list;
	list = n;
	
	struct Node *previousNode = 0;
	struct Node *currentNode = list;
	
	

	if (currentNode->next == 0)
	{
		return list;
	}

	previousNode = currentNode;
	currentNode = currentNode->next;
	
	for (; currentNode != 0; currentNode = currentNode->next)
	{
		if (currentNode->word < previousNode->word)
		{
			//string temp = currentNode->word;
			//currentNode->word = previousNode->word;
			//previousNode->word = temp;

			struct Node *temp = previousNode;
			previousNode = currentNode;
			currentNode = temp;
	
			//struct Node *temp = previousNode->next;
			//previousNode->next = previousNode;
			//currentNode->next = temp;

			
			
		}

		previousNode = currentNode;
	}
	
	return list;            // returning pointer to beginning of the list
}
Last edited on
Why you don't use something like set<Node> or list<Node>?
In set<Node> sorting is done automatically when inserting node.
In list<Node> you can use upper_bound(...) for find place for insertion.
In any case it wuold be quicker (O(ln(n))) than your algorithm (O(n)) and insertion would be done by changing pointers, not moving whole struct.
You start with one of the following situations:

[some other node].next -> previousNode.next -> currentNode.next -> [something]
                  list -> previousNode.next -> currentNode.next -> [something]


You want to end up with:
            [whatever] -> currentNode.next -> previousNode.next -> [something]


That with you knowledge of swapping values should be enough to get you on the right path.
Topic archived. No new replies allowed.