Solution for Sort List


  • -1
    R

    #include<iostream>
    using namespace std;

    struct node
    {
    int val;
    struct node *next;
    };

    void FrontBackSplit(struct node* source,
    struct node** frontRef, struct node** backRef) {
    struct node* fast;
    struct node* slow;
    if (source == NULL || source->next == NULL) { // length < 2 cases
    *frontRef = source;
    *backRef = NULL;
    }
    else {
    slow = source;
    fast = source->next;
    // Advance 'fast' two nodes, and advance 'slow' one node
    while (fast != NULL) {
    fast = fast->next;
    if (fast != NULL) {
    slow = slow->next;
    fast = fast->next;
    }
    }
    // 'slow' is before the midpoint in the list, so split it in two
    // at that point.
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
    }
    }

    struct node* SortedMerge(struct node* a, struct node* b)
    {
    struct node* result;

    if (a == NULL)
    {
    	return b;
    }
    else if (b == NULL)
    {
    	return a;
    }
    else
    {
    	if (a->val < b->val)
    	{
    		result = a;
    		result->next = SortedMerge(a->next, b);
    	}
    	else
    	{
    		result = b;
    		result->next = SortedMerge(a, b->next);
    	}
    }
    
    return result;
    

    }

    void MergeSort(struct node** headRef) {
    struct node* head = headRef;
    struct node
    a;
    struct node* b;
    // Base case -- length 0 or 1
    if ((head == NULL) || (head->next == NULL)) {
    return;
    }
    FrontBackSplit(head, &a, &b); // Split head into 'a' and 'b' sublists
    // We could just as well use AlternatingSplit()
    MergeSort(&a); // Recursively sort the sublists
    MergeSort(&b);
    *headRef = SortedMerge(a, b); // answer = merge the two sorted lists together
    }

    void insertList(struct node** headref, int data)
    {
    struct node *current = *headref;
    struct node * newNode = new node();
    newNode->val = data;
    newNode->next = NULL;

    if (*headref == NULL)
    {
    	*headref = newNode;
    }
    else
    {
    	while (current->next != NULL)
    	{
    		current = current->next;
    	}
    	current->next = newNode;
    }
    

    }

    void PrintList(struct node* head)
    {
    struct node* current = head;
    while (current != NULL)
    {
    cout << current->val << "->";
    current = current->next;
    }

    cout <<"NULL" << endl;
    

    }

    int main()
    {
    struct node *head = NULL;

    insertList(&head, 5);
    insertList(&head, 3);
    insertList(&head, 7);
    insertList(&head, 1);
    insertList(&head, 8);
    insertList(&head, 2);
    insertList(&head, 10);
    insertList(&head, 4);
    
    PrintList(head);
    
    MergeSort(&head);
    
    cout << "Shorted List: " << endl;
    PrintList(head);
    
    return 0;
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.