CODEWITHSUNDEEP
c
Joey Ngo
Joey Ngo

Reputation: 111

Segregate Odd and Even numbers in Linked List, segmentation fault

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

//////////////////////////////////////////////////////////////////////////////////

typedef struct _listnode
{
    int item;
    struct _listnode *next;
} ListNode;         // You should not change the definition of ListNode

typedef struct _linkedlist
{
    int size;
    ListNode *head;
} LinkedList;           // You should not change the definition of LinkedList


//////////////////////// function prototypes /////////////////////////////////////


void moveOddItemsToBack(LinkedList *ll);


void printList(LinkedList *ll);
void removeAllItems(LinkedList *ll);
ListNode * findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);
int removeNode(LinkedList *ll, int index);
void appendNode(LinkedList *ll, int item);

//////////////////////////// main() //////////////////////////////////////////////

int main()
{
    LinkedList ll;
    int c, i, j;
    c = 1;
    //Initialize the linked list 1 as an empty linked list
    ll.head = NULL;
    ll.size = 0;


    printf("1: Insert an integer to the linked list:\n");
    printf("2: Moves all odd integers to the back of the linked list:\n");
    printf("0: Quit:\n");

    while (c != 0)
    {
        printf("Please input your choice(1/2/0): ");
        scanf("%d", &c);

        switch (c)
        {
        case 1:
            printf("Input an integer that you want to add to the linked list: ");
            scanf("%d", &i);
            j = insertNode(&ll, ll.size, i);
            printf("The resulting Linked List is: ");
            printList(&ll);
            break;
        case 2:
            moveOddItemsToBack(&ll); // You need to code this function
            printf("The resulting Linked List after moving odd integers to the back of the Linked List is: ");
            printList(&ll);
            removeAllItems(&ll);
            break;
        case 0:
            removeAllItems(&ll);
            break;
        default:
            printf("Choice unknown;\n");
            break;
        }
    }
    return 0;
}

//////////////////////////////////////////////////////////////////////////////////

void moveOddItemsToBack(LinkedList *ll)
{
    ListNode *cur , *tail, *pre ;

    /* Get tail ptr to the last node */
    tail = ll->head ;
    while (tail->next != NULL)
        tail = tail->next ;

    ListNode *newTail = tail ;

    newTail = tail ;

    /* Start traversing list and put all odd items to tail */
    cur = ll->head ;
    pre = cur ;

    while (cur != tail){
        if(cur->item % 2 != 0) { // <- Segmentation Fault!
            pre->next = cur->next ;
            newTail->next = cur ;
            newTail->next->next = NULL ;
            cur = pre->next ;
            newTail = newTail->next ;
        }
        else {
            pre = cur ;
            cur = cur->next ;
        }
    }
}

void appendNode(LinkedList *ll , int item){
    /* Insert Node to empty list */
    ListNode  *cur;
    if (ll->head == NULL ) {
        ll->head = malloc(sizeof(ListNode));
        ll->head->item = item ;
        ll->size++ ;
    }
    cur = ll->head ;
    /* Append to non-empty */
    if (ll->head != NULL ) {
        while (cur->next != NULL) {
            cur = cur->next ;
        }
        cur->next = malloc(sizeof(ListNode)) ;
        cur->next->item = item ;
        ll->size++ ;
    }
}
//////////////////////////////////////////////////////////////////////////////////

void printList(LinkedList *ll){

    ListNode *cur;
    if (ll == NULL)
        return;
    cur = ll->head;
    if (cur == NULL)
        printf("Empty");
    while (cur != NULL)
    {
        printf("%d ", cur->item);
        cur = cur->next;
    }
    printf("\n");
}


void removeAllItems(LinkedList *ll)
{
    ListNode *cur = ll->head;
    ListNode *tmp;

    while (cur != NULL){
        tmp = cur->next;
        free(cur);
        cur = tmp;
    }
    ll->head = NULL;
    ll->size = 0;
}


ListNode * findNode(LinkedList *ll, int index){

    ListNode *temp;

    if (ll == NULL || index < 0 || index >= ll->size)
        return NULL;

    temp = ll->head;

    if (temp == NULL || index < 0)
        return NULL;

    while (index > 0){
        temp = temp->next;
        if (temp == NULL)
            return NULL;
        index--;
    }

    return temp;
}

int insertNode(LinkedList *ll, int index, int value){

    ListNode *pre, *cur;

    if (ll == NULL || index < 0 || index > ll->size + 1)
        return -1;

    // If empty list or inserting first node, need to update head pointer
    if (ll->head == NULL || index == 0){
        cur = ll->head;
        ll->head = malloc(sizeof(ListNode));
        ll->head->item = value;
        ll->head->next = cur;
        ll->size++;
        return 0;
    }

    // Find the nodes before and at the target position
    // Create a new node and reconnect the links
    if ((pre = findNode(ll, index - 1)) != NULL){
        cur = pre->next;
        pre->next = malloc(sizeof(ListNode));
        pre->next->item = value;
        pre->next->next = cur;
        ll->size++;
        return 0;
    }

    return -1;
}


int removeNode(LinkedList *ll, int index){

    ListNode *pre, *cur;

    // Highest index we can remove is size-1
    if (ll == NULL || index < 0 || index >= ll->size)
        return -1;

    // If removing first node, need to update head pointer
    if (index == 0){
        cur = ll->head->next;
        free(ll->head);
        ll->head = cur;
        ll->size--;

        return 0;
    }

    // Find the nodes before and after the target position
    // Free the target node and reconnect the links
    if ((pre = findNode(ll, index - 1)) != NULL){

        if (pre->next == NULL)
            return -1;

        cur = pre->next;
        pre->next = cur->next;
        free(cur);
        ll->size--;
        return 0;
    }

    return -1;
}

The above is my code, I am trying to achieve 

If the linked list is 2  3  4  7  15  18:
The resulting Linked List after moving odd integers to the back of the Linked List is: 2 4 18 3 7 15

by moving all Odd items to the back of the Linked list. The function of interest would be void moveOddItemsToBack.

I am very confused, as when I use the example given above, 2,3,4,7,15,18. I am able to get the desired output.

However, using an example such as 1,3,4,7,15,18, where the first number is an odd number, i get a segmentation fault at this line. 

while (cur != tail){
        if(cur->item % 2 != 0) { // <- Segmentation Fault!
            pre->next = cur->next ;
            newTail->next = cur ;
            newTail->next->next = NULL ;
            cur = pre->next ;
            newTail = newTail->next ;
        }

Did i do something wrong?

Upvotes: 0

Views: 451

Answers (1)

4386427
4386427

Reputation: 44274

You need special handling of the case cur == ll->head because in that case prev is not a legal previous element. Also you'll have to update ll->head

Like

    if(cur->item % 2 != 0) { // <- Segmentation Fault!
    {
        if (cur == ll->head)
        {
            // Add new code here - perhaps something like
            ll->head = cur->next;
            prev = cur->next;
            newTail->next = cur ;
            newTail->next->next = NULL ;
            cur = ll->head;
        }
        else
        {
            // Your current code
        }

Upvotes: 1

Related Questions