Append last n nodes of a singly LL to the start

raunak jasrasaria 0
Viewed 27

Please help me find the error in the given code, After returning the new head and using the printing function, no output gets displayed

Node *interChange(Node *head, int n){
    Node *tempoo = head;
    Node *temp = head;
    int tot =0;
    
    while(tempoo != NULL){
        tempoo = tempoo->next;
        tot++;
    }
   
    
    int count =0;
    
    while(count < tot-n){
        temp=temp->next;
        count++;
    }
    Node *newHead = temp->next;
    temp->next=NULL;
    Node *newTemp = newHead;
    
    while(newTemp != NULL){
        newTemp = newTemp->next;
    }
    newTemp->next = head;
    
    return newHead;
    
}
linked-list c++
1 Answers

The last statement before the return performs an invalid dereferencing: newTemp->next = head; when at that point it is guaranteed that newTemp is NULL. This leads to undefined behaviour.

Your function returns the new head, so make sure the caller (which you didn't include) will use that new head pointer when printing the list.

Some other remarks:

  • The code does not deal well when the list is empty
  • The code does not deal well when n is greater than the number of nodes in the list, or is negative. It would maybe be a good idea to use modulo arithmetic to bring that value in range.
  • The cutoff point is wrongly calculated. For n is 0, the original head node will still become the new tail (if all the rest is corrected).
  • In C++ you should be using nullptr instead of NULL
  • Calling all your variables something like temp is not helpful. You can do with fewer variables, and use more telling names.

Here is a correction to your function:

Node *interChange(Node *head, int n) {
    if (head == nullptr) return nullptr; // Boundary case
    Node *tail = head;
    int tot = 1; // We already have the head
    // Check whether there is a next node, so we end up with the tail
    while (tail->next != nullptr) {
        tail = tail->next;
        tot++;
    }
    // Make list circular
    tail->next = head;
    // Bring the n argument within a valid range 
    n %= tot;
    // Find new tail
    for (int count = tot - n; count; count--) {
        tail = tail->next; // Reuse tail variable to identify new tail
    }
    // Reuse variable to identify new head
    head = tail->next;
    // Make list non-circular again
    tail->next = nullptr;
    return head;
}

The caller should capture the returned pointer. For instance:

Node *head;
// Initialise head with a list ...
// (your code here)
// And then:
head = interChange(head, 3);
trincot0
Related