Problem1: Write a program that swaps every two nodes in a single linked list. Gi

Question

Problem1:
Write a program that swaps every two nodes in a single linked list.
Given 1 -> 2 -> 3 -> 4 -> 5, it returns 2 -> 1 -> 4 -> 3 -> 5.

Problem2:
Design & implement a stack of integer values that has an additional function 'minimum' that runs in O(1) besides most basic stack functions. e.g. push(5), push(3), push(4), push(2), pop(), and then minimum() should return 3.

Explanation / Answer

a) #include #include /* A linked list node */ struct node { int data; struct node *next; }; /*Function to swap two integers at addresses a and b */ void swap(int *a, int *b); /* Function to pairwise swap elements of a linked list */ void pairWiseSwap(struct node *head) { struct node *temp = head; /* Traverse further only if there are at-least two nodes left */ while(temp != NULL && temp->next != NULL) { /* Swap data of node with its next node's data */ swap(&temp->data, &temp->next->data); /* Move temp by 2 for the next pair */ temp = temp->next->next; } } /* UTILITY FUNCTIONS */ /* Function to swap two integers */ void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } /* Function to add a node at the begining of Linked List */ void push(struct node** head_ref, int new_data) { /* allocate node */ struct node* new_node = (struct node*) malloc(sizeof(struct node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList(struct node *node) { while(node != NULL) { printf("%d ", node->data); node = node->next; } } /* Druver program to test above function */ int main() { struct node *start = NULL; /* The constructed linked list is: 1->2->3->4->5 */ push(&start, 1); push(&start, 2); push(&start, 3); push(&start, 4); push(&start, 5); printf(" Linked list before calling pairWiseSwap() "); printList(start); pairWiseSwap(start); printf(" Linked list after calling pairWiseSwap() "); printList(start); getchar(); return 0; } b) struct MinStack { MinStack *next; MinStack *min; int value; } MinStack *Push(MinStack * stack, int value) { MinStack *top = (MinStack *)malloc(sizeof(MinStack)); top->value = value; top->next = stack; if (stack->min->value min = stack->min }else { top->min = top; } } MinStack *Pop(MinStack * stack, int *poppedValue) { *poppedValue = stack->value; MinStack *top = stack->next; free(stack); return top; } int Min(MinStack *stack) { return stack->min->value; }

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.