Question

C++ language.

struct Node

{

   int data;

   Node *next;

}

Write a function to concatenate two linked lists. Given lists A* = (4, 6) and B* = (3, 7, 12), after return from Concatenate_Lists(Node A*, Node B*) the list A should be changed to be A = (4, 6, 3, 7, 12). Your function should not change B and should not directly link nodes from A to B (i.e. the nodes inserted into A should be copies of the nodes from B.)

Write a function to reverse the nodes in a linked list. The reverse function rearranges the nodes in the list so that their order is reversed. You should do this without creating or destroying nodes.

The function prototype:          void reverse_list(Node*& head);

Write a function that returns the minimum data value in a linked list. Given a linked list A = (4, 5, 10, -1, 0), the function int Find_Max(Node * head) shall return -1.

Write a function to split a linked list into two linked list. Given lists A* = (4, 6, 3, 9), your function shall create new linked lists, A1* = (4, 6) and A2* = (3, 9), after that your function should delete the input linked list A. If the size of A is odd, then list A1* is greater than list A2* by one value. Print out A before splitting, A1, A2, and A after splitting. Your function prototype: void Split_List(Node*& head).

Answer 1

code in C++ with comments (code to copy)

#include <bits/stdc++.h>
using namespace std;

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

Node* Concatenate_Lists(Node *A, Node *B){
        if(B==NULL)
        return A;
        //make a copy of B
        Node *head=new Node();
        head->next=NULL;
        head->data=B->data;
        Node *temp=head;
        while(B->next!=NULL){
                temp->next=new Node();
                temp->next->next=NULL;
                temp->next->data=B->next->data;
                temp=temp->next;
                B=B->next;
        }
        if(A==NULL){
                return head;
        }
        temp = A;
        while(temp->next!=NULL)
                temp=temp->next;
        temp->next=head;
        return A;
}

void reverse_list(Node *&head){
        Node* current = head; 
        Node *prev = NULL, *next = NULL; 
        while (current != NULL) { 
                next = current->next; 
                current->next = prev; 
                prev = current; 
                current = next; 
        } 
        head = prev; 
}

//this  returns the minimum data value in a linked list
//list must have at leadt one element
int Find_Max(Node * head){
        int val = head->data;
        while(head->next!=NULL){
                val = min(val, head->data); 
                head=head->next;
        }
        return val;
}
void printList(Node* head){
        Node* temp=head;
        while(temp!=NULL){
                cout<<temp->data<<" ";
                temp=temp->next;
        }
        cout<<endl;
}
void Split_List(Node*& head){
        //print A before splitting
        cout<<"List A: ";
        printList(head);
        int len=0;
        Node* temp=head;
        while(temp!=NULL){
                temp=temp->next;
                len++;
        }
        int a1_size = (len+1)/2;
        int a2_size = len-a1_size;
        Node* A1=NULL, *A2=NULL;
        temp = A1;
        while(a1_size--){
                if(temp==NULL){
                        A1 = new Node();
                        A1->next=NULL;
                        A1->data=head->data;
                        temp=A1;
                }else{
                        temp->next=new Node();
                        temp->next->next=NULL;
                        temp->next->data=head->data;
                        temp=temp->next;
                }
                Node *to_be_deleted = head;
                head=head->next;
                delete to_be_deleted;
        }
        temp=A2;
        while(a2_size--){
                if(temp==NULL){
                        A2 = new Node();
                        A2->next=NULL;
                        A2->data=head->data;
                        temp=A2;
                }else{
                        temp->next=new Node();
                        temp->next->next=NULL;
                        temp->next->data=head->data;
                        temp=temp->next;
                }
                Node *to_be_deleted = head;
                head=head->next;
                delete to_be_deleted;
        }
        //print A before splitting
        cout<<"List A1: ";
        printList(A1);
        //print A2 before splitting
        cout<<"List A2: ";
        printList(A2);
}
//helper method to create list from array
Node* createListFromArray(int arr[], int n){
        Node* head = new Node();
        head->next=NULL;
        head->data=arr[0];
        Node *temp=head;
        for(int i=1;i<n;i++){
                temp->next=new Node();
                temp->next->next=NULL;
                temp->next->data=arr[i];
                temp=temp->next;
        }
        return head;
}
int main(){
        //Part 1
        int arr1[] = {4,6};
        Node* A = createListFromArray(arr1,2);
        cout<<"A : ";
        printList(A);
        int arr2[] = {3,7,12};
        Node* B = createListFromArray(arr2,3);
        cout<<"B : ";
        printList(B);
        cout<<"calling A = Concatenate_Lists(A, B)"<<endl;
        A = Concatenate_Lists(A, B);
        cout<<"A : ";
        printList(A);
        cout<<"B : ";
        printList(B);
        cout<<endl;

        //Part 2
        cout<<"A : ";
        printList(A);
        cout<<"calling reverse_list(A)"<<endl;
        reverse_list(A);
        cout<<"A : ";
        printList(A);
        cout<<endl;

        //part 3
        int arr3[] = {4, 5, 10, -1, 0};
        A = createListFromArray(arr3,5);
        cout<<"A : ";
        printList(A);
        cout<<"calling max = Find_Max(A) to return minimum data value in the linked list"<<endl;
        int max = Find_Max(A);
        cout<<"max = "<<max<<endl<<endl;

        //part 4
        int arr4[] = {4, 6, 3, 9};
        A = createListFromArray(arr4,4);
        cout<<"A : ";
        printList(A);
        cout<<"calling Split_List(A)"<<endl;
        Split_List(A);
}

Code screenshot

Console Output Screenshot

Let me know in the comments if you have any doubts.
Do leave a thumbs up if this was helpful.