In the code below, I try to change the first node with another node from the list. The problem is that I can't do it, I've been struggling for two days, and I still can't figure it out.
Description code :
- enter the number of nodes from the keyboard.
- pos1 = 1 - the position of the first node in the list
- pos2 - the position of the node to be changed with the first node.
In the function Node *createLinkedList(int n) I create the list of nodes, the function void displayList(Node *head) displays the list, the function void swapFirstNode(Node *head, int pos1, int pos2) should exchange the first node with the node a whose position is read from the keyboard.
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
}Node;
Node *createLinkedList(int n);
void displayList(Node *head);
void swapFirstNode(Node *head, int pos1, int pos2);
int main()
{
int n, pos1, pos2;
Node *HEAD = NULL;
printf("\n Enter the number of nodes : ");
scanf("%d", &n);
HEAD = createLinkedList(n);
displayList(HEAD);
printf("\n Enter first node position to swap : ");
scanf("%d", &pos1);
printf("\n Enter second node position to swap : ");
scanf("%d", &pos2);
if(pos1 == 1 && pos2 != 1)
swapFirstNode(HEAD, pos1, pos2);
displayList(HEAD);
}
Node *createLinkedList(int n)
{
int i, value;
Node *head = NULL;
Node *temp = NULL;
Node *curr = NULL;
head = (struct node*)malloc(sizeof(struct node));
if(head == NULL)
{
printf("\n Memory can not be allocated!");
}
else
{
printf("\n Input data for node 1 : ");
scanf("%d", &value);
head->data = value;
head->next = NULL;
temp = head;
for(i=2; i<=n; i )
{
curr = (struct node *)malloc(sizeof(struct node));
if(curr == NULL)
{
printf(" Memory can not be allocated.");
break;
}
else
{
printf("\n Input data for node %d : ", i);
scanf("%d", &value);
curr->data = value;
curr->next = NULL;
temp->next = curr;
temp = temp->next;
}
}
}
return head;
}
void displayList(Node *head)
{
Node *curr = head;
printf("\n");
printf(" ");
while(curr != NULL)
{
printf("%d->", curr->data);
curr = curr->next;
}
printf("NULL\n");
}
void swapFirstNode(Node *head, int pos1, int pos2)
{
Node *curr = head, *node1 = NULL, *node2 = NULL, *prev_node1 = NULL, *prev_node2 = NULL, *temp = NULL;
int counter = 0, value, i = 1;
/// Find out how many nodes are in list
while(curr != NULL)
{
counter ;
curr = curr->next;
}
if(pos1 < 1 || pos1 > counter || pos2 < 1 || pos2 > counter)
exit(0);
/// Retain the maxim value between two position entered from the keyboard
value = pos1 > pos2 ? pos1 : pos2;
curr = head;
node1 = curr;
while(curr != NULL && i <= value)
{
if(pos2 != 1)
{
/// Set the previous node (the node before the second node), regarding the pos2-1
if(i == (pos2-1))
prev_node2 = curr;
/// Set the seconde node, regarding the pos2 entered from the keyboard
if(i == pos2)
node2 = curr;
}
curr = curr->next;
i ;
}
/// Try to swap the two nodes
if(node1 != NULL && node2 != NULL)
{
if(prev_node2 != NULL)
{
temp = head;
node1->next = node2->next;
node2 = temp;
prev_node2->next = node1;
node2->next = temp->next;
}
}
}
CodePudding user response：
I'm sorry. I get dizzy trying to keep track of all of those counters and pointers and everything.
KISS
The following works quite well swapping the head node with another further down the list. Earlier validation ensures that pos > 1 (the user's idea of "first" node) and pos <= n, the count of the number of nodes in the LL. (ie. The user enters 'swap node 2' and this function is called with n - 1. The function then works with the head being considered node 0.)
Notice that the address of the pointer head is received as a ptr-to-ptr. This allows the function to update the caller's variable. Essential in this case because the function is definitely changing the LL's first node!
Anyway, walk & think your way through these lines. I hope it helps show that fewer moving parts can be more effective.
void swapFirstNode( Node **head, int pos ) {
Node *prev = *head, *cut;
if( pos == 1 ) { // special case of 1st & 2nd swapping
cut = prev->next;
prev->next = prev->next->next;
cut->next = prev;
} else {
while( --pos )
prev = prev->next; // Now pointing at node AHEAD of node to swap out.
cut = prev->next;
Node *cont = cut->next; // Now pointing at continuation (if any)
cut->next = (*head)->next; // Now two heads
prev->next = *head; // head spliced onto 1st section
(*head)->next = cont; // old head joined to continuation
}
*head = cut; // This is the new head!
}
CodePudding user response：
I asked for clarification regarding pos1 but didn't get any so I just disregard that. swapFirstNode will always swap with the first node so pos1 will not be needed.
In order to do the swap, I suggest iterating from head pos2 times, then perform a swap of head->data and the data at the Node you're currently pointing at.
Example:
// pos2 is in the range [0, number of elements)
void swapFirstNode(Node *head, int pos2) {
Node *curr = head;
while(pos2-- > 0 && curr) curr = curr->next;
if(!curr) return; // pos2 was out of bounds
// swap
int tmp = curr->data;
curr->data = head->data;
head->data = tmp;
}
Note: pos2 is zero-based as-is common practice in C. You may present 1-based indices to the user, but I suggest not using 1-based arrays/lists in the rest of the code.
CodePudding user response：
For starters the function createLinkedList has an unpredictable behavior because it creates a node even when the user passes to the function a non-positive value.
Node *createLinkedList(int n)
{
int i, value;
Node *head = NULL;
Node *temp = NULL;
Node *curr = NULL;
head = (struct node*)malloc(sizeof(struct node));
//...
At first it should check the value of the parameter n before starting creating nodes. Also the parameter should have an unsigned integer type as for example size_t because negative values do not make a sense.
The parameter of the function displayList should be declared with qualifier const because the function does not change the displayed list.
void displayList( const Node *head );
In C indices start from 0 not from 1. The index 0 corresponds to the head node.
Calculating the number of nodes in the list
while(curr != NULL)
{
counter ;
curr = curr->next;
}
is inefficient. For example if you want to swap the first two nodes then there is no sense to count all nodes in the list.
And if the user specified invalid positions then the program shall not end abruptly as in your function
if(pos1 < 1 || pos1 > counter || pos2 < 1 || pos2 > counter)
exit(0);
It is enough to report to the user that nodes were not swapped because the user specified invalid positions.
And the pointer to the head node must be passed by reference that is through a pointer to it because the pointer to the head node can be changed within the function.
So the function should be declared like
int swapFirstNode( Node **head, size_t pos1, size_t pos2 );
That is the function returns integer value 1 in case of success or 0 otherwise.
What you need to swap two nodes is to swap the pointers that point to the nodes and their data members next that in turn are pointers.
So write an auxiliary function swap that will swap two pointers.
Here is a demonstration program that shows how it can be done.
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
}Node;
Node * createLinkedList( const int a[], size_t n )
{
Node *head = NULL;
Node **current = &head;
while ( n-- && ( *current = malloc( sizeof( Node ) ) ) != NULL )
{
( *current )->data = *a ;
( *current )->next = NULL;
current = &( *current )->next;
}
return head;
}
void displayList( const Node *head )
{
for ( ; head != NULL; head = head->next )
{
printf( "%d -> ", head->data );
}
puts( "null" );
}
void swap( Node **ptr1, Node **ptr2 )
{
Node *tmp = *ptr1;
*ptr1 = *ptr2;
*ptr2 = tmp;
}
int swapFirstNode( Node **head, size_t pos1, size_t pos2 )
{
int success = 0;
if ( pos1 != pos2 )
{
if ( pos2 < pos1 )
{
size_t tmp = pos1;
pos1 = pos2;
pos2 = tmp;
}
Node **first_node = head;
for ( size_t i = 0; *first_node != NULL && i < pos1; i )
{
first_node = &( *first_node )->next;
}
success = *first_node != NULL;
if ( success )
{
Node **second_node = first_node;
for ( size_t i = 0; *second_node != NULL && i < pos2 - pos1; i )
{
second_node = &( *second_node )->next;
}
success = *second_node != NULL;
if ( success )
{
swap( first_node, second_node );
swap( &( *first_node )->next, &( *second_node )->next );
}
}
}
return success;
}
int main( void )
{
int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
size_t N = sizeof( a ) / sizeof( *a );
Node *head = createLinkedList( a, N );
displayList( head );
swapFirstNode( &head, 0, 1 );
displayList( head );
swapFirstNode( &head, 2, 9 );
displayList( head );
swapFirstNode( &head, 4, 5 );
displayList( head );
}
The program output is
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
1 -> 0 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
1 -> 0 -> 9 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 2 -> null
1 -> 0 -> 9 -> 3 -> 5 -> 4 -> 6 -> 7 -> 8 -> 2 -> null
In fact it is this code snippet
if ( success )
{
swap( first_node, second_node );
swap( &( *first_node )->next, &( *second_node )->next );
}
that swaps two nodes by using the auxiliary function swap that swaps two pointers.
As you can see the function swapFirstNodeis very flexible. It can swap any two nodes of the list. And it indeed swaps two nodes not just data stored in nodes.
Pay attention to that you need to write a function that will clear the list that is that will free all the allocated memory.