Splitting a linked list

Question

Why are the split lists always empty in this program? (It is derived from the code on the Wikipedia page on Linked Lists.)

/* 
    Example program from wikipedia linked list article
    Modified to find nth node and to split the list
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct ns
{
    int data;
    struct ns *next; /* pointer to next element in list */
} node;

node *list_add(node **p, int i)
{
    node *n = (node *)malloc(sizeof(node));
    if (n == NULL)
     return NULL;

    n->next = *p; //* the previous element (*p) now becomes the "next" element */
    *p = n;       //* add new empty element to the front (head) of the list */
    n->data = i;

    return *p;
}

void list_print(node *n)
{
    int i=0;
    if (n == NULL)
    {
     printf("list is empty\n");
    }
    while (n != NULL)
    {
     printf("Value at node #%d = %d\n", i, n->data);
     n = n->next;
        i++;
    }
}

node *list_nth(node *head, int index) {
    node *current = head;
    node *temp=NULL;
    int count = 0; // the index of the node we're currently looking at
    while (current != NULL) {
        if (count == index)
            temp = current;
        count++;
        current = current->next;
    }
    return temp;
}
/* 
This function is to split a linked list:
Return a list with nodes starting from index 'int ind' and
step the index by 'int step' until the end of list.
*/
node *list_split(node *head, int ind, int step) {
    node *current = head;
    node *temp=NULL;
    int count = ind; // the index of the node we're currently looking at
    temp = list_nth(current, ind);
    while (current != NULL) {
        count = count+step;
        temp->next = list_nth(head, count);
        current = current->next;
    }

    return temp; /* return the final stepped list */
}

int main(void)
{
    node *n = NULL, *list1=NULL, *list2=NULL, *list3=NULL, *list4=NULL;
    int i;
    /* List with 30 nodes */
    for(i=0;i<=30;i++){
        list_add(&n, i);
    }
    list_print(n);

    /* Get 1th, 5th, 9th, 13th, 18th ... nodes of n etc */ 

    list1 = list_split(n, 1, 4);

    list_print(list1);

    list2 = list_split(n, 2, 4); /* 2, 6, 10, 14 etc */   
    list_print(list2);

    list3 = list_split(n, 3, 4); /* 3, 7, 11, 15 etc */   
    list_print(list3);

    list3 = list_split(n, 4, 4); /* 4, 8, 12, 16 etc */   
    list_print(list4);

    getch();
    return 0;
}

Answer 1

 temp = list_nth(current, ind);

 while (current != NULL) {
        count = count+step;
        temp->next = list_nth(head, count);
        current = current->next;
    }

You are finding the correct item to begin the split at, but look at what happens to temp from then on ... you only ever assign to temp->next.

You need to keep track of both the head of your split list and the tail where you are inserting new items.

Answer 2

The program, actually, has more than one problem.

• Indexes are not a native way to address linked list content. Normally, pointers to nodes or iterators (which are disguised pointers to nodes) are used. With indexes, accessing a node has linear complexity (O(n)) instead of constant O(1).

• Note that list_nth returns a pointer to a "live" node within a list, not a copy. By assigning to temp->next in list_split, you are rewiring the original list instead of creating a new one (but maybe it's intentional?)

• Within list_split, temp is never advanced, so the loop just keeps attaching nodes to the head instead of to the tail.

• Due to use of list_nth for finding nodes by iterating through the whole list from the beginning, list_split has quadratic time (O(n**2)) instead of linear time. It's better to rewrite the function to iterate through the list once and copy (or re-attach) required nodes as it passes them, instead of calling list_nth. Or, you can write current = list_nth(current, step).

• [EDIT] Forgot to mention. Since you are rewiring the original list, writing list_nth(head, count) is incorrect: it will be travelling the "short-cirquited" list, not the unmodified one.

Answer 3

Your description of what list_split is supposed to return is pretty clear, but it's not clear what is supposed to happen, if anything, to the original list. Assuming it's not supposed to change:

node *list_split(node *head, int ind, int step) {
    node *current = head;
    node *newlist=NULL;
    node **end = &newlist;
    node *temp = list_nth(current, ind);

    while (temp != NULL) {
        *end = (node *)malloc(sizeof(node));
        if (*end == NULL) return NULL;
        (*end)->data = temp->data;
        end = &((*end)->next);
        temp = list_nth(temp, step);
    }

    return newlist; /* return the final stepped list */
}

(You probably want to factor a list_insert routine out of that that inserts a new node at a given location. list_add isn't very useful since it always adds to the beginning of the list.)

Answer 4

I also notice that it looks like you are skipping the first record in the list when you are calculating *list_nth*. Remember is C we normally start counting at zero.

Draw out a Linked List diagram and follow your logic:

[0]->[1]->[2]->[3]->[4]->[5]->[6]->[7]->[8]->[9]->...->[10]->[NULL]