#include <stdio.h>
#include <stdlib.h>
  
typedef struct Node{
int data;
struct Node *link;} NODE;

  NODE *InsertNode(NODE *pList, NODE * pPre, int item);
void PrintList(NODE *pList);

int main(void)
{
     NODE *start=NULL;
     NODE *pPre, *pCur;
     int x;

     printf("Enter a sequence of integers followed by a nonnumeric character:\n");

     while (scanf("%d",&x) == 1)
     {
          SearchList(start,&pPre,&pCur,x);
          start = InsertNode(start,pPre,x);
      }

       PrintList(start);
       return 0;
}

NODE *InsertNode(NODE *pList, NODE *pPre, int item)
{
       NODE *pNew;
       pNew = (NODE *)malloc(sizeof(NODE));

      if (pNew == NULL)
      {
          printf("Not enough memory");
         exit(1);
       }

       pNew->data = item;

       if (pPre == NULL)
      {
         /*Inserting before first node or to empty list */
          pNew->link = pList;
          pList = pNew;
       }
      else
     {
       /* Inserting in middle or at end */
        pNew->link = pPre->link;
        pPre->link = pNew;
      }
       return pList;

}

void PrintList(NODE *pList)
{
     NODE * pWalker;
     int lineCount = 0;
     pWalker = pList;

     printf("\nList contains:\n");

     while (pWalker)
     {
          if(++lineCount > 10)
          {
             lineCount = 1;
             printf("\n");
           }
        printf("%3d ",pWalker->data);
        pWalker = pWalker->link;
      }

     printf("\n");
     return;

}

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

typedef struct Node{
        int data;
        struct Node *link;
} NODE;

NODE *InsertNode(NODE *pList, NODE * pPre, int item);
NODE *DeleteNode(NODE *pList, NODE *pPre, NODE *pCur);
NODE *MergeList (NODE *pList, NODE *pList2);
NODE *AddNode   (NODE *pList, int data);

int SearchList(NODE *pList, NODE **pPre, NODE **pCur, int target);
void PrintList(NODE *pList);

int main(void)
{
        // Initilizing the head nodes of the 3 lists
        NODE *start_list1=NULL;
        NODE *start_list2=NULL;
        NODE *start_mergelist=NULL;

        NODE *pPre, *pCur;
        int x;

        // Iniitializes the .txt files
        FILE *list1;
        FILE *list2;
        FILE *merged;

        // Opens the .txt files and checks to see if there is an error
        list1=fopen("list1.txt","r+t");
        if(list1==NULL)
        {
                printf("Error opening list1.txt \n");
                exit(0);
        }
        list2=fopen("list2.txt","r+t");
        if(list2==NULL)
        {
                printf("Error opening list2.txt \n");
                exit(0);
        }

        // Loop: Places each element of the .txt file into linked list
        while(fscanf(list1,"%d",&x)==1)
        {
                SearchList(start_list1, &pPre, &pCur, x);
                start_list1 = InsertNode(start_list1,pPre,x);
        }
        while(fscanf(list2,"%d",&x)==1)
        {
                SearchList(start_list2, &pPre, &pCur, x);
                start_list2 = InsertNode(start_list2,pPre,x);
        }

        //Calls function MergedList and stores in another linked list

        start_mergelist=MergeList(start_list1, start_list2);

        printf("\n List 1: \n");
        PrintList(start_list1);
        printf("\n List 2: \n");
        PrintList(start_list2);
        printf("\n The Merged List of List1 & List2: \n");
        PrintList(start_mergelist);


// Write to merged.txt file
        merged = fopen("merged.txt", "w");
        fprintf(merged,PrintList(start_mergelist));


        fclose(merged);

        return 0;
}
/* ===================InsertNode=============================
        This function inserts a single node into a linked list.
        Pre:        pList is pointer to the list; may be NULL
                        pPre points to new node's logical predecessor
                        item contains data to be inserted
        Post:        returns the head pointer
*/
NODE *InsertNode(NODE *pList, NODE *pPre, int item)
{
        NODE *pNew;
        pNew = (NODE *)malloc(sizeof(NODE));
        if (pNew == NULL)
        {
                printf("Not enough memory");
                exit(1);
        }
        pNew->data = item;
        if (pPre == NULL)
        {
                /*Inserting before first node or to empty list */
                pNew->link = pList;
                pList = pNew;
        }
        else
        {
                /* Inserting in middle or at end */
                pNew->link = pPre->link;
                pPre->link = pNew;
        }
        return pList;
}

/* ===================SearchList=============================
        Given key value, finds the location of a node in the linked list which is
sorted.
        Pre:        pList points to a head node
                        pPre points to variable to receive predecessor
                        pCur points to variable to receive current node
                        target is key being sought
        Post:        pCur points to first node with equal/greater key or NULL is target
> key of last node
                        pPre points to largest node smaller than key or NULL is target < key of
first node
                        returns 1 if found, 0 if not found
*/
int SearchList(NODE *pList, NODE **pPre, NODE **pCur, int target)
{
        int found = 0;

        *pPre = NULL;
        *pCur = pList;

        /* Start the search from the beginning */
        while (*pCur != NULL && target > (*pCur)->data)
        {
                *pPre = *pCur;
                *pCur = (*pCur)->link;
        }
        if (*pCur && target == (*pCur)->data)
                found = 1;

        return found;
}
/* ===================PrintList=============================
        Traverse and print a linked list.
        Pre:        pList points to a head node
        Post:        List has been printed
*/
void PrintList(NODE *pList)
{
        NODE * pWalker;
        int lineCount = 0;

        pWalker = pList;
        printf("\nList contains:\n");

        while (pWalker)
        {
                if(++lineCount > 10)
                {
                        lineCount = 1;
                        printf("\n");
                }
                printf("%3d ",pWalker->data);
                pWalker = pWalker->link;
        }
        printf("\n");
        return;
}
/*=============MergeList===========================
        Merges two lists.
        Pre:        pList1 points to the head node of list 1
                        pList2 points to the head node of list 2
        Post:        Returns head node of merged list.
*/
NODE *MergeList(NODE *pList1, NODE *pList2)
{
        NODE *pWalker, *pPre, *pCur;
        NODE *start=NULL;
        pWalker = pList1;
        while(pWalker)
        {
                start =AddNode(start,pWalker->data);
                pWalker=pWalker->link;
        }
        return start;
}

/*================AddNode============================
        Adds Nodes. Does not allow duplicates.
        pre:        pList points to head of list
                        data is data to be inserted
        post:        returns pointer to head of list
*/
NODE *AddNode(NODE *pList, int data)
{
        NODE *pPre;
        NODE *pCur;
        bool found;
        found = SearchList(pList, &pPre, &pCur, data);
        if(found)
                return(pList);
        return InsertNode(pList,pPre,data);
}