2025 CSCI2100E Lab Session #1

Time limit: 2000ms
Memory limit: 256mb

Description:

In this exercise, we use the linked lists to maintain two sequences of distinct integers, one denoted as linked list A and the another one denoted as linked list B. Given a positive integer k, we may pick one integer a from A, and one integer b from B, such that a + b = k. In this problem, you are required to find out how many such pairs exist for the given k and linked lists A and B.

Fill in the code for the following functions, in the positions indicated by the comment '// code here'.

Compute the number of pairs of integers, one from A and one from B, such that their sum is k.
int NumberOfSumToK(List headA, List headB, int k); 
- You can only visit the input linked list headA and headB but not change them. Finally, return the required number of pairs.

Sample Input 1:
4
4 10 1 7
5
7 3 4 11 2
10

Sample Output 1:
Input the number of integers in A:
Input these integers:
Input the number of integers in B:
Input these integers:
Input k:
Number of pairs summed to k:
1


Sample Input 2:
3
1 0 2 
3
0 -1 2
1

Sample Output 2:
Input the number of integers in A:
Input these integers:
Input the number of integers in B:
Input these integers:
Input k:
Number of pairs summed to k:
2


-------------------------Copy the following code, complete it and submit-------------------------


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

typedef struct linked_list_node{
    int value;
    struct linked_list_node* next;
} Node;

typedef Node* List;

int NumberOfPairsSumToK(List headA, List headB, int k)
{
    int numberOfPairs = 0;
    // code here
    
}

int main()
{
    List headA = NULL;
    List headB = NULL;
    int n, m, k;
    int value;

    printf("Input the number of integers in A:\n");
    scanf("%d", &n);
    printf("Input these integers:\n");
    for(int i=0; i<n; i++)
    {
        scanf("%d", &value);
	Node *ptr = (List)malloc(sizeof(Node)); // allocate a piece of memory for the new node
    	ptr->value = value;
	ptr->next = headA;
        headA = ptr;
    }

    printf("Input the number of integers in B:\n");
    scanf("%d", &m);
    printf("Input these integers:\n");
    for(int i=0; i<m; i++)
    {
        scanf("%d", &value);
        Node *ptr = (List)malloc(sizeof(Node)); // allocate a piece of memory for the new node
    	ptr->value = value;
	ptr->next = headB;
        headB = ptr;
    }
    printf("Input k:\n");
    scanf("%d", &k);

    int noOfPairs;
    noOfPairs = NumberOfPairsSumToK(headA, headB, k);

    printf("Number of pairs summed to k:\n");
    printf("%d\n", noOfPairs);
    return 0;
}





-------------------------------------------End of Code-------------------------------------------