AZ 3/1/2013 Question 1. I used Daniel's method and one list traversal (O(n)). A slight modification of my solution from Wednesday is using the do-while loop instead of the while loop, so that the last node in the original list is not omitted. This code can be compiled. In linux, compile with "gcc az1.c -o example1", then run with "./example1". I…

az1.c

#include <stdio.h>

struct n {
    int v;
    struct n* next;
};

struct n* split_list(struct n* head, int pivot) {
    struct n* cur = head;
    struct n* lh = NULL; struct n* lt = NULL;
    struct n* rh = NULL; struct n* rt = NULL;
    if (!cur || !cur->next) return head;
    
    // Walk through the linked list and build the sublists.
    do {
        if (cur->v <= pivot) {
            if (!lh) {
                // Left list has not been created yet.
                lh = cur;
                lt = cur;
            } else {
                // Append current node to the end of left list.
                lt->next = cur;
                lt = cur;
            }
        } else {
            if (!rh) {
                // Right list has not been created yet.
                rh = cur;
                rt = cur;
            } else {
                // Append current node to the end of right list.
                rt->next = cur;
                rt = cur;
            }
        }
        cur = cur->next;
    } while(cur);
    
    // Join the lists, if necessary.
    if (lt) lt->next = rh;
    if (rt) rt->next = NULL;
    if (lh) return lh;
    else return rh;
}


/* TESTING FRAMEWORK */

void walk_list(struct n* head) {
    // Walk through the linked list and print out the values of the nodes:
    unsigned int ctr = 0;
    struct n* cur = head;
        if (!head) {
        printf("No nodes in linked list.\n");
        return;
    }
    
    while(cur->next) {
        ctr++;
        printf("Node %u: value %d\n", ctr, cur->v); 
        cur = cur->next;
    }
}

void test_implementation() {
    int pivot = 5;
    struct n a;
    struct n b;
    struct n c;
    struct n d;
    struct n e;
    struct n f;
    struct n g;
    
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &f;
    f.next = &g;
    g.next = NULL;
    
    a.v = 2;
    b.v = 4;
    c.v = 10;
    d.v = 8;
    e.v = 5;
    f.v = 9;
    g.v = 8;
    
    printf("Unpartitioned list:\n");
    walk_list(&a);
    
    struct n* new_head = split_list(&a, pivot);
    printf("\nPartitioned list:\n");
    walk_list(new_head);
}

void main() {
    test_implementation();
}

//