CS221 - Quiz 1 Solution

cs221_quiz_1_solution.cpp

// Statement: Suppose we have one way linked list. Write a function to add a node in the linked list such that the resulting list is a sorted one.

#include<iostream>

using namespace std;

class List {

private:

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

    Node *ListHead;

public:

    List() {
        ListHead = nullptr;
    }


    int addSorted(int v) {
        Node *newNode = new Node;
        newNode->value = v;
        newNode->next = nullptr;
        Node *TempNode = ListHead;

        if (ListHead == nullptr || ListHead->value >= v) {
            newNode->next = ListHead;
            ListHead = newNode;
            return 0;

        } else {
            while (TempNode->next != nullptr && TempNode->next->value < newNode->value) {
                TempNode = TempNode->next;
            }

            newNode->next = TempNode->next;
            TempNode->next = newNode;
        }

        return 0;
    }

    void display() {
        Node *TempNode = ListHead;
        while (TempNode != nullptr) {
            cout << TempNode->value << "  ";
            TempNode = TempNode->next;
        }
    }
};

int main() {
    List dataList;
    dataList.addSorted(343);
    dataList.addSorted(35);
    dataList.addSorted(55);
    dataList.addSorted(10);
    dataList.addSorted(5);
    dataList.addSorted(100);
    dataList.addSorted(4);
    dataList.addSorted(2);
    dataList.addSorted(1);
    dataList.addSorted(353);
    dataList.display();

    return 0;
}