I'm trying to figure out how to manipulate linked lists. I want to remove the end node of a given linked list and add this to the end of another given linked list.

For some reason I can not get my pointers right, well- at least that is where I think the problem lays.

(This method sits in a while loop, so one list keeps getting smaller while the other one grows.)

void movenode(struct Node **cards,struct Node **column)
{
    struct Node *head = NULL;
    struct Node *tmp,*head1 = *cards;
    struct Node *tmp2,*head2 = *column;

    if (*cards == NULL || (*cards)->next == NULL){
        return;
    }
    while (tmp->next != NULL) {
        head->next = tmp;
        tmp = tmp->next;
    }
    while (tmp2->next != NULL) {
        tmp2 = tmp2->next;
    }
    head->next = NULL;
    tmp2->data = tmp;
    tmp2->next = NULL;


    *cards = head1;
    *column = head2;
}

Hope someone is able to help me better understand this.

CodePudding user response：

For some reason I can not get my pointers right, well.. atleast that is where I think the problem lays.

You're right, but it's a little more than that. For example, after struct Node *head = NULL; nothing modifies the value in head, so every time you do head->next you're accessing memory at "NULL a small offset" (and will probably crash).

To remove the last entry from a singly linked list, you have to find the entry before the last entry (so that you can modify its next); and to add an entry to a linked list you have to find the last entry (so that you can modify its next). With this in mind we can break it into 5 parts:

• Do sanity checks

• Find the entry before the last entry in the *cards list

• Remove the last entry in the *cards list

• Find the last entry in the *column list

• Add the (removed) entry to the end of the *columns list

You can implement each of these 5 pieces one at a time (and test them). This is an important part of programming - breaking more complex stuff into simpler easier things.

The resulting code might look something like (untested):

void movenode(struct Node **cards,struct Node **column) {
    struct Node *temp = *cards;
    struct Node *removed;

    // Do sanity checks

    if (temp == NULL) {
        return;
    }

    // Find the entry before the last entry in the `*cards` list

    if(temp->next != NULL) {
        while(temp->next->next != NULL) {
            temp = temp->next;
        }
     }

    // Remove the last entry in the `*cards` list

    if(temp == NULL) {
        // The last entry was the first entry
        removed = temp;
        *cards = NULL;
    } else {
        removed = temp->next;
        temp->next = NULL;
    }

    // Find the last entry in the `*column` list

    temp = *column;
    if(temp != NULL) {
        while(temp->next != NULL) {
            temp = temp->next;
        }
    }

    // Add the (removed) entry to the end of the `*columns` list       

    if(temp == NULL) {
        // There was no last entry (list was empty)
        *column = removed;
    } else {
        temp->next = removed;
    }
 }

CodePudding user response：

I'm not entirely sure about the mechanics of your solution so I'll offer a separate implementation and solution.

typedef struct Node {
    void *data;
    struct Node *next;
}

void poppush(Node *popHead, Node *pushHead) {
    Node *pushLastNode = pushHead;
    while (pushLastNode->next != NULL) {
        pushLastNode = pushLastNode->next;
    }

    Node *popLastNode = popHead;
    while (popLastNode->next != NULL) {
        popLastNode = popLastNode->next;
    }

    Node *popSecondLastNode = popHead;
    while (popSecondLastNode->next != popLastNode) {
        popSecondLastNode = popSecondLastNode->next;
    }

    popSecondLastNode->next = NULL;
    pushLastNode->next = popLastNode;
}

However, for operations such as these, I would recommend using a doubly-linked list and/or create some functions dedicated to managing the lists.