Ace11
BAN USERIn this solution you can exchange the two nodes within a single traversal of the linked list. Not syntactically correct.
The premise is that if there are n nodes in the linked list, the head node is the nth node from the end.
assumption: single linked list
head = pointer to head of the list
n = nth node from start and end
n_start = null //pointer to nth node from start
n_start_prev = null //pointer to node whose next points to n_start
n_end = null //pointer to nth node from end
n_end_prev = null //pointer to node whose next points to n_end
temp = null //temporary pointer used while swapping
ptr = head //starting point of traversal
ptr_prev = null //points to previous node of ptr
count = 0 // stores which number of node we are pointing to during traversal
if(ptr == null){
//empty linked list, exit
}
//traversal of linked list
//find n_start and n_end
while(ptr!=null){
count++;
if(count == n){
n_start = ptr;
n_start_prev = ptr_prev;
n_end = head;
n_end_prev = null;
}
else if(count > n){
n_end_prev = n_end;
n_end = n_end->next;
}
ptr_prev = ptr;
ptr = ptr->next;
}
if(count < n){
//not enough nodes in linked list, exit
}
//do the swapping now
if(n_start_prev != null){
n_start_prev->next = n_end;
}
if(n_end_prev != null){
n_end_prev->next = n_start;
}
temp = n_start->next;
n_start->next = n_end->next;
n_end->next = temp;
Essentially the second statement is asking compiler to allocate memory for the string literal, which is read only. For a complete explanation please refer to the anwers on stack overflow question -
stackoverflow.com/questions/1577765/why-must-a-pointer-to-a-char-array-need-strcpy-to-assign-characters-to-its-array
Taking your example, if n=5 and length = 8. when count = 5, n_start will have 5th node and n_end will point to head. after that for every increment of count, n_end will be progressed by 1. so when count =6, n_end will have 2nd element, and when count = 8, n_end will point to 4th node(which happens to be the 5th element from end). Thus, n_end should end up pointing to n places from the end which is what we want.
- Ace11 October 24, 2012