Friday, February 8, 2013

Appending Last N node of Linked list to beginning

Question: Append the last n nodes of a linked list to the beginning of the list

eg: 1->2->3->4->5->6

if n=2

5->6->1->2->3->4

Solution: This is the same approach as the previous problem.Start traversing till you traverse n elements.Start another traverse in same loop after meeting above condition (there will be always gap of n nodes between these to pointers) when first pointer reach to end of linked list second pointer will be n node behind. Just change the pointer .

node *prepend(node * root, int k)
{
node *prev, *curr;
curr = root;
for (int i = 0; i < k; i++) {
curr = curr->next;
if (curr == NULL)
return NULL;
}
prev = root;
while (curr->next != NULL) {
curr = curr->next;
prev = prev->next;
}
curr->next = root;
root = prev->next;
prev->next = NULL;
return root;
}

No comments: