Segregate even and odd nodes in a Linked List

Given a Linked List of integers, write a function to modify the linked list such that all even numbers appear before all the odd numbers in the modified linked list. Also, keep the order of even and odd numbers same.

Examples:
Input: 17->15->8->12->10->5->4->1->7->6->NULL
Output: 8->12->10->4->6->17->15->5->1->7->NULL

Input: 8->12->10->5->4->1->6->NULL
Output: 8->12->10->4->6->5->1->NULL

// If all numbers are even then do not change the list
Input: 8->12->10->NULL
Output: 8->12->10->NULL

// If all numbers are odd then do not change the list
Input: 1->3->5->7->NULL
Output: 1->3->5->7->NULL

#include "linkedlist.h"
#include

NODE* createLL(int maxNode)
{
        int index;
        NODE* headNode=NULL;

        for (index = 0; index <= maxNode; index++)
        {
                headNode = addAtHead(headNode, rand()%100);
        }
        return headNode;
}

NODE* segregateEvenOdd(NODE* headNode)
{
        NODE* currentNode = headNode;
        NODE* lastNode = headNode;
        NODE* previousNode = NULL;
        int length = 0;

        /* Find lastNode and length */
        while(currentNode != NULL)
        {
                lastNode = currentNode;
                currentNode = currentNode->next;
                length++;
        }

        currentNode = headNode;
        while(length)
        {
                /* push OddNumber node to last */
                if (currentNode->data % 2 == 1)
                {
                        if (headNode != currentNode)
                        {
                                previousNode->next = currentNode->next;
                                lastNode->next = currentNode;
                                lastNode = currentNode;
                                currentNode->next = NULL;
                                currentNode = previousNode->next;
                        }
                        else
                        {
                                lastNode->next = headNode;
                                lastNode = headNode;
                                headNode = headNode->next;
                                currentNode->next = NULL;
                                currentNode = headNode;
                        }
                }
                else
                {
                        previousNode = currentNode;
                        currentNode = currentNode->next;
                }
                length--;
        }

        return headNode;
}

/* Driver program */
int main()
{
    NODE* headNode=createLL(10);

    printList(headNode);

        headNode = segregateEvenOdd(headNode);

        printList(headNode);
}

Write a C program to remove duplicates from a sorted linked list.

#include
#include "linkedlist.h"

#define LL_LIMIT 6
#define LL_DUP1 4

NODE* createLL()
{
        int index=LL_LIMIT;
        NODE* headNode = NULL;
        while(index > 0)
        {
                headNode = addAtHead(headNode, index);
                if (index == LL_DUP1)
                {
                        headNode = addAtHead(headNode, index);
                }
                index--;
        }
        return headNode;
}

int removeDupNode(NODE* headNode)
{
        NODE* dupNode;
        if (headNode == NULL)
        {
                printf("List is Empty\n");
                return 1;
        }

        while(headNode->next != NULL)
        {
                if(headNode->data == headNode->next->data)
                {
                        printf("Duplicate data is %d\n", headNode->next->data);
                        dupNode = headNode->next;
                        headNode->next = dupNode->next;
                        free(dupNode);
                }
                headNode = headNode->next;
        }
        return 0;
}

int main()
{
        NODE* headNode = NULL;

        headNode = createLL();

        displayAll(headNode);

        if(!removeDupNode(headNode))
        {
                displayAll(headNode);
        }
}

Find Middle of Linked List

#include
#include "linkedlist.h"

#define LL_LIMIT 6
int main()
{
    int midData;
    int index=LL_LIMIT;
    NODE* headNode=NULL;
    NODE* oneStepPtr=NULL;
    NODE* twoStepPtr=NULL;

    /* Create LL*/
    while(index > 0)
    {
        headNode = addAtHead(headNode, index);
        index--;
    }

    /* Display LL*/
    displayAll(headNode);

    oneStepPtr = headNode;
    twoStepPtr = headNode;

    /* Increment step pointers till the end */
    while(twoStepPtr != NULL &&
          twoStepPtr->next != NULL &&
          twoStepPtr->next->next != NULL)
    {
        oneStepPtr = oneStepPtr->next;
        twoStepPtr = twoStepPtr->next->next;
    }
    midData = oneStepPtr->data;

    printf("Middle of LL contains %d\n", midData);
    return 0;
}

Find the Loop in the linked list and remove the loop from it

int detectLoop(NODE* headNode)
{
       NODE* oneStepPtr = headNode;
       NODE* twoStepPtr = headNode;
       int isLoop = 0;

       while(twoStepPtr != NULL
                 && twoStepPtr->next != NULL
                 )
       {
               oneStepPtr = oneStepPtr->next;
               twoStepPtr = twoStepPtr->next->next;

               if (twoStepPtr == oneStepPtr)
               {
                       isLoop = 1;
                       break;
               }
       }
       return isLoop;
}

/* Call only when loop exists */
void removeLoop(NODE* headNode)
{
       /* find Loop Node */
       NODE* oneStepPtr = headNode;
       NODE* twoStepPtr = headNode;
       NODE* loopNode = headNode;

       while(twoStepPtr != NULL
             && twoStepPtr->next != NULL
            )
   	{
       	oneStepPtr = oneStepPtr->next;
       	twoStepPtr = twoStepPtr->next->next;

       	if (twoStepPtr == oneStepPtr)
       	{
                       loopNode = oneStepPtr;
           		break;
       	}
   	}


       /* Find  loopLength */
       NODE* currentNode = loopNode;
       int loopLength = 0;
       while (currentNode != loopNode
                  || loopLength == 0)
       {
               loopLength++;
               currentNode = currentNode->next;
       }


       /* Offset headNode by loopLength */
       currentNode = headNode;
       NODE* offSetNode = NULL;
       NODE* tailNode = NULL;
       int offSetLength = 0;

       while(offSetLength < loopLength)         {                 tailNode = currentNode;                 currentNode = currentNode->next;
               offSetLength++;
       }
       offSetNode = currentNode;


       /* find tailNode, when currentNode and offSetNode meets, but one */
       currentNode = headNode;
       while(offSetNode != currentNode)
       {
               tailNode = offSetNode;
               offSetNode = offSetNode->next;
               currentNode = currentNode->next;
       }

       tailNode->next = NULL;
}

Write a recursive approach to reverse a link list.

void recursiveReverse(NODE** headNode)
{
        NODE* firstNode;
        NODE* restOfNodes;

        if(headNode == NULL)
        {
                printf("List is Empty\n");
                return;
        }

        firstNode = *headNode;
        restOfNodes = firstNode->next;

        if (restOfNodes == NULL)
        {
                return;
        }

        recursiveReverse(&restOfNodes);

        firstNode->next->next = firstNode;
        firstNode->next = NULL;

        *headNode = restOfNodes;
}

Write a program to return the nth node from the end of a linked list.

#include "linkedlist.h"
#include

#define LL_LIMIT 10

/* Create LL */
NODE* createLL()
{
        int index=0;
        NODE* headNode = NULL;
        while(index <= LL_LIMIT)
        {
                headNode = addAtHead(headNode, ++index);
        }
        return headNode;
}

/* get Nth Node from Last */
int getNthNodeLast(NODE* headNode, int nodeNum)
{
                NODE* currentNode1 = headNode;
                NODE* currentNode2 = headNode;
                int count = 0;

                while(currentNode1 != NULL)
                {
                                count++;
                                currentNode1 = currentNode1->next;
                                if(count > nodeNum)
                                {
                                                currentNode2 = currentNode2->next;
                                }
                }

                return currentNode2->data;
}

/* Driver program to test above functions */
int main()
{
                NODE* headNode = NULL;
                headNode = createLL();

                displayAll(headNode);
                printf("3rd Node is %d\n", getNthNodeLast(headNode, 3));
}

Write a C program to remove duplicates from a sorted linked list.

#include
#include "linkedlist.h"

#define LL_LIMIT 6
#define LL_DUP1 4

NODE* createLL()
{
        int index=LL_LIMIT;
        NODE* headNode = NULL;
        while(index > 0)
        {
                headNode = addAtHead(headNode, index);
                if (index == LL_DUP1)
                {
                        headNode = addAtHead(headNode, index);
                }
                index--;
        }
        return headNode;
}

int removeDupNode(NODE* headNode)
{
        NODE* dupNode;
        if (headNode == NULL)
        {
                printf("List is Empty\n");
                return 1;
        }

        while(headNode->next != NULL)
        {
                if(headNode->data == headNode->next->data)
                {
                        printf("Duplicate data is %d\n", headNode->next->data);
                        dupNode = headNode->next;
                        headNode->next = dupNode->next;
                        free(dupNode);
                }
                headNode = headNode->next;
        }
        return 0;
}

int main()
{
        NODE* headNode = NULL;

        headNode = createLL();

        displayAll(headNode);

        if(!removeDupNode(headNode))
        {
                displayAll(headNode);
        }
}

Find Middle of Linked List

#include
#include "linkedlist.h"

#define LL_LIMIT 6
int main()
{
    int midData;
    int index=LL_LIMIT;
    NODE* headNode=NULL;
    NODE* oneStepPtr=NULL;
    NODE* twoStepPtr=NULL;

    /* Create LL*/
    while(index > 0)
    {
        headNode = addAtHead(headNode, index);
        index--;
    }

    /* Display LL*/
    displayAll(headNode);

    oneStepPtr = headNode;
    twoStepPtr = headNode;

    /* Increment step pointers till the end */
    while(twoStepPtr != NULL &&
          twoStepPtr->next != NULL &&
          twoStepPtr->next->next != NULL)
    {
        oneStepPtr = oneStepPtr->next;
        twoStepPtr = twoStepPtr->next->next;
    }
    midData = oneStepPtr->data;

    printf("Middle of LL contains %d\n", midData);
    return 0;
}

Stack using One Queue

Implement a stack using a queue. The operations need not be neccesarily O(1).

#include "queueimplll.h"

typedef struct queue QUEUE;
typedef struct queue_node QUEUE_NODE;

int queuepush( QUEUE *q1, int val)
{

        /* In an empty Q, push the val straight*/
        if (q1->first == 0 &&
        q1->last == 0)
        {
                enqueue( q1, val);
                return 0;
        }

        /* enQ val*/
        if (enqueue(q1, val))
        {
                printf("ERROR: enqueue q2\n");
        }


        /* deQ, enQ by 1 short of QLength*/
        int first_value;
        int qlength = queue_length(q1) - 1;
        while(qlength--)
        {
                dequeue(q1, &first_value);
                enqueue(q1, first_value);
        }

        return 0;
}

/*Driver Program*/
int main()
{
        QUEUE queue1;
        int index;

        init_queue(&queue1);

        for (index = 10; index <= 100; index += 10)
        {
                queuepush( &queue1, index);
        }

        int value = 0;
        index = 0;
        while (!queue_empty_p(&queue1))
        {
                dequeue( &queue1, &value);
                printf("%d : %d\n", index++, value);
        }
}

Stack using two queues

Implement a stack using two queues. The operations need not be neccesarily O(1).

#include stdio.h
#include "queueimplll.h"

typedef struct queue QUEUE;
typedef struct queue_node QUEUE_NODE;

int queuepush( QUEUE *q1, QUEUE *q2, int val)
{

        /* If first queue is empty, enqueue  val straight away*/
        if (q1->first == 0 &&
        q1->last == 0)
        {
                enqueue( q1, val);
                return 0;
        }

        /* Enqueue val into second queue*/
        if (enqueue(q2, val))
        {
                printf("ERROR: enqueue q2\n");
        }

        /* Move (deQ, enQ) from q1 to q2 */
        int first_value;
        while (!queue_empty_p(q1))
        {
                dequeue(q1, &first_value);
                enqueue(q2, first_value);
        }

        /* Move (deQ, enQ) from q2 to q1*/
        while (!queue_empty_p(q2))
        {
                dequeue(q2, &first_value);
                enqueue(q1, first_value);
        }
        /* q1 is ready to be poped up*/

        queue_empty_p(q2);
        return 0;
}

/* Driver program */
int main()
{
        QUEUE queue1, queue2;
        int index;

        init_queue(&queue1);
        init_queue(&queue2);

        /* Push into queue1 */
        srand(time(NULL));
        for (index = 0; index <= 100; index++)
        {
                queuepush( &queue1, &queue2, (rand() % 100) + 1);
        }

        /* Pop from queue1*/
        int value = 0;
        index = 0;
        while (!queue_empty_p(&queue1))
        {
                dequeue( &queue1, &value);
                printf("%d : %d\n", index++, value);
        }
}

Queue with two stacks

Implement a queue using two stacks. The operations need not be neccesarily O(1).

/* Include Stack Implementation (using Array)*/
#include "stackimplarray.h"

void queuepush(STACK* st1, STACK* st2, int val)
{
        /* If first stack is empty, push the value straight down */
        if (st1->size == 0)
        {
                st1->items[st1->size++] = val;
                return;
        }

        /* Pop all elements of first stack
           and push it into second stack */
        while(st1->size != 0)
        {
                push(st2, pop(st1));
        }

        /* Push value onto second stack */
        push(st2, val);

    /* Pop all elements of second stack
           and push it into first stack */
        while(st2->size != 0)
        {
                push(st1, pop(st2));
        }
}


/* Driver code to test above functions*/
int main()
{
        STACK stack1, stack2;
        int i;
        for(i=1; i<=10; i++)
        {
                queuepush(&stack1, &stack2, i * 100);
        }

        while(stack1.size != 0)
        {
                printf("%d\n", pop(&stack1));
        }
}