Adobe Interview Question
Software Engineer in TestsCountry: United States
code for inserting a node in sorted cylic list.
void insert(struct node* aNode, int x) {
if (!aNode) {
aNode = (struct node*) malloc(sizeof(struct node));
aNode->data = x;
aNode->next = aNode;
return;
}
struct node* p = aNode;
struct node* prev = NULL;
do {
prev = p;
p = p->next;
if (x <= p->data && x >= prev->data) break;
if ((prev->data > p->data) && (x < p->data || x > prev->data)) break;
} while (p != aNode);
struct node* newNode = (struct node*) malloc(sizeof(struct node));
newNode->data = x;
newNode->next = p;
prev->next = newNode;
}
Assume Head node of the circular list contains minimum value
- nsdxnsk August 01, 20121. Compare circular.Head.Data to linear.Head.Data, if liniar's Data is smaller, replace circular Head, and move linear's pointer to next.
2. Do 1 until linear.Node.Data > circular.Head.Data
3. Do normal merge sort for those 2 under condition of
while (circular.Node.Next != circular.Node.Head) // If it equals to Head, it means it gets back to Head pointer
4. After the while loop, if still linear pointer is in the middle, insert Nodes at the last of cirsular list.