Lab Sheet 2: Linked Lists

DSA Programming Solutions | Instructor: Prof. N L Bhanu Murthy

Authors

PARTH MUNJAL

AKARSH JAIN

Published

March 30, 2026

Q1: The Palindrome Check

Description: Check if a Singly Linked List is a Palindrome. Challenge: Solve in-place (using O(1) extra space).

Sample Input

5
1 2 3 2 1

Sample Output

True

Solution

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* createList(int n) {
    struct Node *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        scanf("%d", &newNode->data);
        newNode->next = NULL;
        if (!head) head = tail = newNode;
        else { tail->next = newNode; tail = newNode; }
    }
    return head;
}

void freeList(struct Node* head) {
    while (head) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }
}

struct Node* reverse(struct Node* head) {
    struct Node *prev = NULL, *curr = head, *next = NULL;
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

bool isPalindrome(struct Node* head) {
    if (!head || !head->next) return true;
    struct Node *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    slow->next = reverse(slow->next);
    struct Node *p1 = head, *p2 = slow->next;
    while (p2) {
        if (p1->data != p2->data) return false;
        p1 = p1->next;
        p2 = p2->next;
    }
    return true;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    struct Node* head = createList(n);
    printf("%s\n", isPalindrome(head) ? "True" : "False");
    freeList(head);
    return 0;
}

Q2: Segregate Even and Odd Values

Description: All Even numbers appear before all Odd numbers while maintaining relative order.

Sample Input

7
17 15 8 12 10 5 4

Sample Output

8 12 10 4 17 15 5

Solution

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* createList(int n) {
    struct Node *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        scanf("%d", &newNode->data);
        newNode->next = NULL;
        if (!head) head = tail = newNode;
        else { tail->next = newNode; tail = newNode; }
    }
    return head;
}

void freeList(struct Node* head) {
    while (head) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }
}

struct Node* segregateEvenOdd(struct Node* head) {
    struct Node *evenHead = NULL, *evenTail = NULL;
    struct Node *oddHead = NULL, *oddTail = NULL;
    struct Node *curr = head;

    while (curr) {
        if (curr->data % 2 == 0) {
            if (!evenHead) { evenHead = evenTail = curr; }
            else { evenTail->next = curr; evenTail = curr; }
        } else {
            if (!oddHead) { oddHead = oddTail = curr; }
            else { oddTail->next = curr; oddTail = curr; }
        }
        curr = curr->next;
    }
    if (evenTail) evenTail->next = oddHead;
    if (oddTail) oddTail->next = NULL;
    return evenHead ? evenHead : oddHead;
}

void printList(struct Node* node) {
    while (node) { printf("%d%s", node->data, node->next ? " " : ""); node = node->next; }
    printf("\n");
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    struct Node* head = createList(n);
    head = segregateEvenOdd(head);
    printList(head);
    freeList(head);
    return 0;
}

Q3: Rotate List

Description: Rotate a Singly Linked List to the Right by K places.

Sample Input

5
10 20 30 40 50
2

Sample Output

40 50 10 20 30

Solution

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* createList(int n) {
    struct Node *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        scanf("%d", &newNode->data);
        newNode->next = NULL;
        if (!head) head = tail = newNode;
        else { tail->next = newNode; tail = newNode; }
    }
    return head;
}

void freeList(struct Node* head) {
    while (head) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }
}

struct Node* rotateRight(struct Node* head, int k) {
    if (!head || k == 0) return head;
    int len = 1;
    struct Node* tail = head;
    while (tail->next) { tail = tail->next; len++; }
    k %= len;
    if (k == 0) return head;
    
    tail->next = head;
    for (int i = 0; i < len - k; i++) tail = tail->next;
    head = tail->next;
    tail->next = NULL;
    return head;
}

int main() {
    int n, k;
    if (scanf("%d", &n) != 1) return 1;
    struct Node* head = createList(n);
    if (scanf("%d", &k) != 1) { freeList(head); return 1; }
    head = rotateRight(head, k);
    struct Node* curr = head;
    while (curr) { printf("%d%s", curr->data, curr->next ? " " : ""); curr = curr->next; }
    printf("\n");
    freeList(head);
    return 0;
}

Q4: Insert After Two (Sum & Skip)

Description: Calculate sum of pairs and insert after the second node.

Sample Input

4
2 4 5 3

Sample Output

2 4 6 5 3 8

Solution

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* createList(int n) {
    struct Node *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        scanf("%d", &newNode->data);
        newNode->next = NULL;
        if (!head) head = tail = newNode;
        else { tail->next = newNode; tail = newNode; }
    }
    return head;
}

void freeList(struct Node* head) {
    while (head) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }
}

void insertSumAfterPairs(struct Node* head) {
    struct Node* curr = head;
    while (curr && curr->next) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = curr->data + curr->next->data;
        newNode->next = curr->next->next;
        curr->next->next = newNode;
        curr = newNode->next;
    }
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    struct Node* head = createList(n);
    insertSumAfterPairs(head);
    struct Node* curr = head;
    while (curr) { printf("%d%s", curr->data, curr->next ? " " : ""); curr = curr->next; }
    printf("\n");
    freeList(head);
    return 0;
}

Q5: Swap Nodes in Pairs

Description: Swap actual Node pointers (next), not data values.

Sample Input

4
10 20 30 40

Sample Output

20 10 40 30

Solution

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* createList(int n) {
    struct Node *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        scanf("%d", &newNode->data);
        newNode->next = NULL;
        if (!head) head = tail = newNode;
        else { tail->next = newNode; tail = newNode; }
    }
    return head;
}

void freeList(struct Node* head) {
    while (head) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }
}

struct Node* swapPairs(struct Node* head) {
    if (!head || !head->next) return head;
    struct Node* first = head;
    struct Node* second = head->next;
    first->next = swapPairs(second->next);
    second->next = first;
    return second;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    struct Node* head = createList(n);
    head = swapPairs(head);
    struct Node* curr = head;
    while (curr) { printf("%d%s", curr->data, curr->next ? " " : ""); curr = curr->next; }
    printf("\n");
    freeList(head);
    return 0;
}

Q6: Increasing Subsequence from First Element

Description: Remove the next node if its value is less than or equal to the current node.

Sample Input

4
5 3 6 1

Sample Output

5 -> 6

Solution

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* createList(int n) {
    struct Node *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        scanf("%d", &newNode->data);
        newNode->next = NULL;
        if (!head) head = tail = newNode;
        else { tail->next = newNode; tail = newNode; }
    }
    return head;
}

void freeList(struct Node* head) {
    while (head) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }
}

void removeNonIncreasing(struct Node* head) {
    struct Node* curr = head;
    while (curr && curr->next) {
        if (curr->next->data <= curr->data) {
            struct Node* temp = curr->next;
            curr->next = curr->next->next;
            free(temp);
        } else {
            curr = curr->next;
        }
    }
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    struct Node* head = createList(n);
    removeNonIncreasing(head);
    struct Node* curr = head;
    while (curr) { printf("%d%s", curr->data, curr->next ? " -> " : ""); curr = curr->next; }
    printf("\n");
    freeList(head);
    return 0;
}

Q7: Move all Occurrences to the End

Description: Rearrange so all nodes with value X are moved to the end.

Sample Input

7
1 2 3 2 4 2 5
2

Sample Output

1 3 4 5 2 2 2

Solution

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* createList(int n) {
    struct Node *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        scanf("%d", &newNode->data);
        newNode->next = NULL;
        if (!head) head = tail = newNode;
        else { tail->next = newNode; tail = newNode; }
    }
    return head;
}

void freeList(struct Node* head) {
    while (head) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }
}

struct Node* moveXToEnd(struct Node* head, int x) {
    if (!head) return NULL;
    struct Node dummyNormal, dummyX;
    struct Node *pNormal = &dummyNormal, *pX = &dummyX, *curr = head;
    dummyNormal.next = dummyX.next = NULL;
    
    while (curr) {
        if (curr->data == x) {
            pX->next = curr;
            pX = pX->next;
        } else {
            pNormal->next = curr;
            pNormal = pNormal->next;
        }
        curr = curr->next;
    }
    pX->next = NULL;
    pNormal->next = dummyX.next;
    return dummyNormal.next;
}

int main() {
    int n, x;
    if (scanf("%d", &n) != 1) return 1;
    struct Node* head = createList(n);
    if (scanf("%d", &x) != 1) { freeList(head); return 1; }
    head = moveXToEnd(head, x);
    struct Node* curr = head;
    while (curr) { printf("%d%s", curr->data, curr->next ? " " : ""); curr = curr->next; }
    printf("\n");
    freeList(head);
    return 0;
}

Q8: Find new Element

Description: Size N array A, size N+2 array B (reshuffled A + 2 random). Find the two added elements.

Sample Input

3
1 2 3
3 6 2 3 1

Sample Output

3 6

Solution

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

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    int *A = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &A[i]);
    
    int m = n + 2;
    int *B = (int *)malloc(m * sizeof(int));
    for (int i = 0; i < m; i++) scanf("%d", &B[i]);
    
    int maxVal = 0;
    for(int i=0; i<m; i++) if(B[i] > maxVal) maxVal = B[i];
    int *freq = (int *)calloc(maxVal + 1, sizeof(int));
    for(int i=0; i<m; i++) freq[B[i]]++;
    for(int i=0; i<n; i++) freq[A[i]]--;
    
    int found = 0;
    for(int i=0; i<=maxVal; i++) {
        while(freq[i] > 0) {
            printf("%s%d", found ? " " : "", i);
            found = 1;
            freq[i]--;
        }
    }
    printf("\n");
    
    free(A); free(B); free(freq);
    return 0;
}

Q9: Same Parity Count

Description: Count how many times an even number at an even index and odd at odd index when sorted.

Sample Input

3
2 5 4

Sample Output

1,0

Solution

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

int compare(const void *a, const void *b) { return (*(int*)a - *(int*)b); }

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    int *arr = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    
    qsort(arr, n, sizeof(int), compare);
    int even_count = 0, odd_count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 == 0 && i % 2 == 0) even_count++;
        else if (arr[i] % 2 != 0 && i % 2 != 0) odd_count++;
    }
    printf("%d,%d\n", even_count, odd_count);
    free(arr);
    return 0;
}

Q10: Maximum Elements in a Range

Description: Max elements such that max - min \le K.

Sample Input

5
1
2 1 1 3 2

Sample Output

Solution

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

int compare(const void *a, const void *b) { return (*(int*)a - *(int*)b); }

int main() {
    int n, k;
    if (scanf("%d", &n) != 1) return 1;
    if (scanf("%d", &k) != 1) return 1;
    int *arr = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    
    qsort(arr, n, sizeof(int), compare);
    int i = 0, j = 0, maxElements = 0;
    while (j < n) {
        if (arr[j] - arr[i] <= k) {
            if (j - i + 1 > maxElements) maxElements = j - i + 1;
            j++;
        } else i++;
    }
    printf("%d\n", maxElements);
    free(arr);
    return 0;
}

--- title: "Lab Sheet 2: Linked Lists" subtitle: "DSA Programming Solutions | Instructor: Prof. N L Bhanu Murthy" author: - "PARTH MUNJAL" - "AKARSH JAIN" date: last-modified format: html: toc: true toc-depth: 3 code-tools: true number-sections: false theme: cosmo robots: noindex --- # Q1: The Palindrome Check **Description:** Check if a Singly Linked List is a Palindrome. Challenge: Solve in-place (using $O(1)$ extra space). ::: {.callout-note title="Sample Input"} ``` 5 1 2 3 2 1 ``` ::: ::: {.callout-note title="Sample Output"} ``` True ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> #include <stdbool.h> struct Node { int data; struct Node* next; }; struct Node* createList(int n) { struct Node *head = NULL, *tail = NULL; for (int i = 0; i < n; i++) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); scanf("%d", &newNode->data); newNode->next = NULL; if (!head) head = tail = newNode; else { tail->next = newNode; tail = newNode; } } return head; } void freeList(struct Node* head) { while (head) { struct Node* temp = head; head = head->next; free(temp); } } struct Node* reverse(struct Node* head) { struct Node *prev = NULL, *curr = head, *next = NULL; while (curr) { next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } bool isPalindrome(struct Node* head) { if (!head || !head->next) return true; struct Node *slow = head, *fast = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } slow->next = reverse(slow->next); struct Node *p1 = head, *p2 = slow->next; while (p2) { if (p1->data != p2->data) return false; p1 = p1->next; p2 = p2->next; } return true; } int main() { int n; if (scanf("%d", &n) != 1) return 1; struct Node* head = createList(n); printf("%s\n", isPalindrome(head) ? "True" : "False"); freeList(head); return 0; } ``` ::: # Q2: Segregate Even and Odd Values **Description:** All Even numbers appear before all Odd numbers while maintaining relative order. ::: {.callout-note title="Sample Input"} ``` 7 17 15 8 12 10 5 4 ``` ::: ::: {.callout-note title="Sample Output"} ``` 8 12 10 4 17 15 5 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; struct Node* createList(int n) { struct Node *head = NULL, *tail = NULL; for (int i = 0; i < n; i++) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); scanf("%d", &newNode->data); newNode->next = NULL; if (!head) head = tail = newNode; else { tail->next = newNode; tail = newNode; } } return head; } void freeList(struct Node* head) { while (head) { struct Node* temp = head; head = head->next; free(temp); } } struct Node* segregateEvenOdd(struct Node* head) { struct Node *evenHead = NULL, *evenTail = NULL; struct Node *oddHead = NULL, *oddTail = NULL; struct Node *curr = head; while (curr) { if (curr->data % 2 == 0) { if (!evenHead) { evenHead = evenTail = curr; } else { evenTail->next = curr; evenTail = curr; } } else { if (!oddHead) { oddHead = oddTail = curr; } else { oddTail->next = curr; oddTail = curr; } } curr = curr->next; } if (evenTail) evenTail->next = oddHead; if (oddTail) oddTail->next = NULL; return evenHead ? evenHead : oddHead; } void printList(struct Node* node) { while (node) { printf("%d%s", node->data, node->next ? " " : ""); node = node->next; } printf("\n"); } int main() { int n; if (scanf("%d", &n) != 1) return 1; struct Node* head = createList(n); head = segregateEvenOdd(head); printList(head); freeList(head); return 0; } ``` ::: # Q3: Rotate List **Description:** Rotate a Singly Linked List to the Right by K places. ::: {.callout-note title="Sample Input"} ``` 5 10 20 30 40 50 2 ``` ::: ::: {.callout-note title="Sample Output"} ``` 40 50 10 20 30 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; struct Node* createList(int n) { struct Node *head = NULL, *tail = NULL; for (int i = 0; i < n; i++) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); scanf("%d", &newNode->data); newNode->next = NULL; if (!head) head = tail = newNode; else { tail->next = newNode; tail = newNode; } } return head; } void freeList(struct Node* head) { while (head) { struct Node* temp = head; head = head->next; free(temp); } } struct Node* rotateRight(struct Node* head, int k) { if (!head || k == 0) return head; int len = 1; struct Node* tail = head; while (tail->next) { tail = tail->next; len++; } k %= len; if (k == 0) return head; tail->next = head; for (int i = 0; i < len - k; i++) tail = tail->next; head = tail->next; tail->next = NULL; return head; } int main() { int n, k; if (scanf("%d", &n) != 1) return 1; struct Node* head = createList(n); if (scanf("%d", &k) != 1) { freeList(head); return 1; } head = rotateRight(head, k); struct Node* curr = head; while (curr) { printf("%d%s", curr->data, curr->next ? " " : ""); curr = curr->next; } printf("\n"); freeList(head); return 0; } ``` ::: # Q4: Insert After Two (Sum & Skip) **Description:** Calculate sum of pairs and insert after the second node. ::: {.callout-note title="Sample Input"} ``` 4 2 4 5 3 ``` ::: ::: {.callout-note title="Sample Output"} ``` 2 4 6 5 3 8 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; struct Node* createList(int n) { struct Node *head = NULL, *tail = NULL; for (int i = 0; i < n; i++) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); scanf("%d", &newNode->data); newNode->next = NULL; if (!head) head = tail = newNode; else { tail->next = newNode; tail = newNode; } } return head; } void freeList(struct Node* head) { while (head) { struct Node* temp = head; head = head->next; free(temp); } } void insertSumAfterPairs(struct Node* head) { struct Node* curr = head; while (curr && curr->next) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = curr->data + curr->next->data; newNode->next = curr->next->next; curr->next->next = newNode; curr = newNode->next; } } int main() { int n; if (scanf("%d", &n) != 1) return 1; struct Node* head = createList(n); insertSumAfterPairs(head); struct Node* curr = head; while (curr) { printf("%d%s", curr->data, curr->next ? " " : ""); curr = curr->next; } printf("\n"); freeList(head); return 0; } ``` ::: # Q5: Swap Nodes in Pairs **Description:** Swap actual Node pointers (next), not data values. ::: {.callout-note title="Sample Input"} ``` 4 10 20 30 40 ``` ::: ::: {.callout-note title="Sample Output"} ``` 20 10 40 30 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; struct Node* createList(int n) { struct Node *head = NULL, *tail = NULL; for (int i = 0; i < n; i++) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); scanf("%d", &newNode->data); newNode->next = NULL; if (!head) head = tail = newNode; else { tail->next = newNode; tail = newNode; } } return head; } void freeList(struct Node* head) { while (head) { struct Node* temp = head; head = head->next; free(temp); } } struct Node* swapPairs(struct Node* head) { if (!head || !head->next) return head; struct Node* first = head; struct Node* second = head->next; first->next = swapPairs(second->next); second->next = first; return second; } int main() { int n; if (scanf("%d", &n) != 1) return 1; struct Node* head = createList(n); head = swapPairs(head); struct Node* curr = head; while (curr) { printf("%d%s", curr->data, curr->next ? " " : ""); curr = curr->next; } printf("\n"); freeList(head); return 0; } ``` ::: # Q6: Increasing Subsequence from First Element **Description:** Remove the next node if its value is less than or equal to the current node. ::: {.callout-note title="Sample Input"} ``` 4 5 3 6 1 ``` ::: ::: {.callout-note title="Sample Output"} ``` 5 -> 6 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; struct Node* createList(int n) { struct Node *head = NULL, *tail = NULL; for (int i = 0; i < n; i++) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); scanf("%d", &newNode->data); newNode->next = NULL; if (!head) head = tail = newNode; else { tail->next = newNode; tail = newNode; } } return head; } void freeList(struct Node* head) { while (head) { struct Node* temp = head; head = head->next; free(temp); } } void removeNonIncreasing(struct Node* head) { struct Node* curr = head; while (curr && curr->next) { if (curr->next->data <= curr->data) { struct Node* temp = curr->next; curr->next = curr->next->next; free(temp); } else { curr = curr->next; } } } int main() { int n; if (scanf("%d", &n) != 1) return 1; struct Node* head = createList(n); removeNonIncreasing(head); struct Node* curr = head; while (curr) { printf("%d%s", curr->data, curr->next ? " -> " : ""); curr = curr->next; } printf("\n"); freeList(head); return 0; } ``` ::: # Q7: Move all Occurrences to the End **Description:** Rearrange so all nodes with value X are moved to the end. ::: {.callout-note title="Sample Input"} ``` 7 1 2 3 2 4 2 5 2 ``` ::: ::: {.callout-note title="Sample Output"} ``` 1 3 4 5 2 2 2 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; struct Node* createList(int n) { struct Node *head = NULL, *tail = NULL; for (int i = 0; i < n; i++) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); scanf("%d", &newNode->data); newNode->next = NULL; if (!head) head = tail = newNode; else { tail->next = newNode; tail = newNode; } } return head; } void freeList(struct Node* head) { while (head) { struct Node* temp = head; head = head->next; free(temp); } } struct Node* moveXToEnd(struct Node* head, int x) { if (!head) return NULL; struct Node dummyNormal, dummyX; struct Node *pNormal = &dummyNormal, *pX = &dummyX, *curr = head; dummyNormal.next = dummyX.next = NULL; while (curr) { if (curr->data == x) { pX->next = curr; pX = pX->next; } else { pNormal->next = curr; pNormal = pNormal->next; } curr = curr->next; } pX->next = NULL; pNormal->next = dummyX.next; return dummyNormal.next; } int main() { int n, x; if (scanf("%d", &n) != 1) return 1; struct Node* head = createList(n); if (scanf("%d", &x) != 1) { freeList(head); return 1; } head = moveXToEnd(head, x); struct Node* curr = head; while (curr) { printf("%d%s", curr->data, curr->next ? " " : ""); curr = curr->next; } printf("\n"); freeList(head); return 0; } ``` ::: # Q8: Find new Element **Description:** Size N array A, size N+2 array B (reshuffled A + 2 random). Find the two added elements. ::: {.callout-note title="Sample Input"} ``` 3 1 2 3 3 6 2 3 1 ``` ::: ::: {.callout-note title="Sample Output"} ``` 3 6 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int main() { int n; if (scanf("%d", &n) != 1) return 1; int *A = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &A[i]); int m = n + 2; int *B = (int *)malloc(m * sizeof(int)); for (int i = 0; i < m; i++) scanf("%d", &B[i]); int maxVal = 0; for(int i=0; i<m; i++) if(B[i] > maxVal) maxVal = B[i]; int *freq = (int *)calloc(maxVal + 1, sizeof(int)); for(int i=0; i<m; i++) freq[B[i]]++; for(int i=0; i<n; i++) freq[A[i]]--; int found = 0; for(int i=0; i<=maxVal; i++) { while(freq[i] > 0) { printf("%s%d", found ? " " : "", i); found = 1; freq[i]--; } } printf("\n"); free(A); free(B); free(freq); return 0; } ``` ::: # Q9: Same Parity Count **Description:** Count how many times an even number at an even index and odd at odd index when sorted. ::: {.callout-note title="Sample Input"} ``` 3 2 5 4 ``` ::: ::: {.callout-note title="Sample Output"} ``` 1,0 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int compare(const void *a, const void *b) { return (*(int*)a - *(int*)b); } int main() { int n; if (scanf("%d", &n) != 1) return 1; int *arr = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); qsort(arr, n, sizeof(int), compare); int even_count = 0, odd_count = 0; for (int i = 0; i < n; i++) { if (arr[i] % 2 == 0 && i % 2 == 0) even_count++; else if (arr[i] % 2 != 0 && i % 2 != 0) odd_count++; } printf("%d,%d\n", even_count, odd_count); free(arr); return 0; } ``` ::: # Q10: Maximum Elements in a Range **Description:** Max elements such that max - min $\le K$. ::: {.callout-note title="Sample Input"} ``` 5 1 2 1 1 3 2 ``` ::: ::: {.callout-note title="Sample Output"} ``` 4 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int compare(const void *a, const void *b) { return (*(int*)a - *(int*)b); } int main() { int n, k; if (scanf("%d", &n) != 1) return 1; if (scanf("%d", &k) != 1) return 1; int *arr = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); qsort(arr, n, sizeof(int), compare); int i = 0, j = 0, maxElements = 0; while (j < n) { if (arr[j] - arr[i] <= k) { if (j - i + 1 > maxElements) maxElements = j - i + 1; j++; } else i++; } printf("%d\n", maxElements); free(arr); return 0; } ``` :::