Thread: Insert linked list into another Linked list

I have a linked list comprised of chars like so...

Code:

node1 - "p" 
    node2 - "o" 
        node3 - "p"

I need a function that will take in three perameters...

node *replaceChar(node *head, char key, char *str)Stipulations of this function. head is the head of the list, 'key' and 'str' are guaranteed to contain alphanumeric characters only (A-Z, a-z, and 0-9). str can range from 1 to 1023 characters (inclusively).

So if I call this function with these perameters..

Code:

node *head == /*the head of the list to be examined*/

char key == "p"char *str == "dog"The new list will look like this...

node1 - 'd' 
  node2 - 'o' 
    node3 - 'g' 
      node4 - 'o' 
        node5 - 'd' 
          node6 - 'o' 
            node7 - 'g'

All instances of 'p' were replaced with 'dog'

I have a toString function which takes in a string and converts it to a linked list and returns the head. So assume that you can call the function on str = "dog" so...

Code:

toString(str) == /*this will return the head to the list made from the str*/

If it's unclear what my question is...I am stumped on how to write the replaceChar function the one that takes in three perameters.. I can create a new list using the string and find all instances of key but making the new list fit into the old list without losing the pointers is killing me.

The trick is knowing how to insert a new node into a list. For your example, you find an instance of 'p' and then replace the value with 'd'. Then insert the remaining characters from str as new nodes after 'p'. Repeat starting after the newest node by looking for another instance of 'p'. It's fairly straightforward (warning: code written in haste and not tested):

Code:

node *replaceChar(node *head, char key, char *str)
    {
    node *p = head;

    while ((p = findNode(p, key))
        {
        char *nextChar = str;

        p->data = *nextChar++;

        while (*nextChar != '\0')
            {
            p = insertAfter(p, *nextChar++);
            }
        }

    return head;
    }

As I won't do your homework for you, I've left findNode and insertAfter as exercises since those are the key tasks for this exercise.

Because, OP, you say don't know what you're talking about, inserting a linked list into another is relatively painless.

Find an insertion spot, let's say between node C and node D. We know that C->next = D and D->next = NULL or node E or some other node.

We then have a linked list that we shall call, insertList. This list begins with node X and ends with node Z. We say for the sake of example that X->next = Y and Y->next = Z and Z->next = NULL.

We want to insert insertList in-between C and D. So all we have to do is switch around the pointers. We say C->next = X and Z->next = D. Granted, this requires keeping a 'head' and 'tail' pointer of your list to insert. head would point at X and tail would point at Z. So you say C->next = head of insertList and the tail of insertList->D.

I think that should do it. If I'm wrong, please, someone correct me, I'd hate to give bad advice but I think this should do it, tbh.