• 1

• 31.8k
• 15
• 77
• 202

(See the initial iteration.)

Continuing from Merge sorting a singly-linked list in C, I have incorporated the points made by @vnp.

Now it looks like this:

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct linked_list_node {
 int value;
 struct linked_list_node* next;
} linked_list_node;
/*******************************************************************************
* This fuction converts the command line arguments to a linked list. *
*******************************************************************************/
static linked_list_node* build_linked_list_from_args(int argc, const char* argv[])
{
 if (argc <= 1)
 {
 return NULL;
 }
 linked_list_node* list = calloc(argc - 1, sizeof(*list));
 for (size_t node_index = 0; node_index < argc - 1; ++node_index)
 {
 list[node_index].value = atoi(argv[1 + node_index]);
 list[node_index].next = node_index == argc - 2 ?
 NULL :
 &list[node_index + 1];
 }
 return list;
}
/*******************************************************************************
* This function prints the entire linked list to stdout. *
*******************************************************************************/
static void print(linked_list_node* head)
{
 printf("[");
 linked_list_node* current_node = head;
 if (current_node)
 {
 printf("%d", current_node->value);
 current_node = current_node->next;
 }
 while (current_node)
 {
 printf(" %d", current_node->value);
 current_node = current_node->next;
 }
 printf("]");
}
/*******************************************************************************
* This function merges stabily the two input lists that are expected to be *
* sorted. *
*******************************************************************************/
static linked_list_node* merge(linked_list_node* left_head,
 linked_list_node* right_head)
{
 linked_list_node* merged_list_head;
 linked_list_node* merged_list_tail;
 if (right_head->value < left_head->value)
 {
 merged_list_head = right_head;
 merged_list_tail = right_head;
 right_head = right_head->next;
 }
 else
 {
 merged_list_head = left_head;
 merged_list_tail = left_head;
 left_head = left_head->next;
 }
 while (left_head && right_head)
 {
 if (right_head->value < left_head->value)
 {
 merged_list_tail->next = right_head;
 merged_list_tail = right_head;
 right_head = right_head->next;
 }
 else
 {
 merged_list_tail->next = left_head;
 merged_list_tail = left_head;
 left_head = left_head->next;
 }
 }
 merged_list_tail->next = left_head ? left_head : right_head;
 return merged_list_head;
}
/*******************************************************************************
* This function splits the input linked list in two sublists and returns the *
* head of the right one. *
*******************************************************************************/
static linked_list_node* split(linked_list_node* head)
{
 linked_list_node* slow = head;
 linked_list_node* fast = head;
 linked_list_node* prev_slow = NULL;
 while (fast && fast->next)
 {
 prev_slow = slow;
 slow = slow->next;
 fast = fast->next->next;
 }
 linked_list_node* right_sublist_head = prev_slow->next;
 prev_slow->next = NULL;
 return right_sublist_head;
}
/*******************************************************************************
* This function implements the actual sorting routine. *
*******************************************************************************/
static linked_list_node* sort_impl(linked_list_node* head)
{
 if (!head->next)
 {
 return head;
 }
 linked_list_node* right_sublist_head = split(head);
 return merge(sort_impl(head), sort_impl(right_sublist_head));
}
/*******************************************************************************
* This function sorts the input linked list whose the first node is 'head'. *
*******************************************************************************/
linked_list_node* sort(linked_list_node* head)
{
 if (!head || !head->next)
 {
 return head;
 }
 return sort_impl(head);
}
int main(int argc, const char * argv[]) {
 linked_list_node* head = build_linked_list_from_args(argc, argv);
 print(head);
 puts("");
 head = sort(head);
 print(head);
 puts("");
 return 0;
}

As always, any critique is much appreciated.