Thread: Insert linked list into another Linked list

  1. #1
    Registered User
    Join Date
    Jun 2013

    Lightbulb Insert linked list into another Linked list

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

    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..

    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...

    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.

  2. #2
    Registered User
    Join Date
    Jun 2013
    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):
    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.

  3. #3
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    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.

  4. #4
    young grasshopper jwroblewski44's Avatar
    Join Date
    May 2012
    Where the sidewalk ends
    When I begin work on a new data structure, or any new concept, using a whiteboard to write out what I'm trying to do helps a LOT. Draw yourself a diagram of what the linked list looks like, and then work step-by-step to insert the string wherever the character to be replaced is found.

    You will definitely need a function that inserts a node at a given point in the list, which would look something like:

    This particular list maintains the same node as the head of the list.

    typedef struct list_node
            char data;
            struct list_node * next;
    } node;
    void insert_node( node * insert_start , node * node_to_insert );
    And a function that is used to create a new list node:

    node * alloc_node( char data );
    That is the groundwork of what I would do.
    "Simplicity is the ultimate sophistication." - Leonardo da Vinci

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Insert a node into the end of a linked list
    By aw1742 in forum C Programming
    Replies: 4
    Last Post: 10-12-2011, 03:50 PM
  2. Insert into position of Linked List
    By Suchy in forum C++ Programming
    Replies: 2
    Last Post: 02-18-2008, 10:02 AM
  3. insert sort linked list???
    By vanella*Flavor in forum C++ Programming
    Replies: 4
    Last Post: 10-25-2005, 07:42 PM
  4. Insert node in a linked list.
    By antonis in forum C Programming
    Replies: 2
    Last Post: 10-22-2005, 02:30 PM
  5. Insert in Linked List ...
    By yescha in forum C Programming
    Replies: 4
    Last Post: 11-28-2001, 04:23 AM

Tags for this Thread