Merge sorting linked lists

linkedlist.c

#include "linkedlist.h"

/*
 * Create a new LinkedList node
 */
node *create(int data, node *next)
{
  node *new_node = (node*)malloc(sizeof(node));

  if (new_node == NULL) {
    printf("Error creating new node\n");
    exit(0);
  }

  new_node->data = data;
  new_node->next = next;

  return new_node;
}

/*
 * Add a node to the start of the list
 */
node *prepend(node *head, int data)
{
  node *new_node = create(data, head);
  head = new_node;
  return head;
}

/*
 * Add a node to the end of the list
 */
node *append(node *head, int data)
{
  node *cursor = head;

  while (cursor->next != NULL)
    cursor = cursor->next;

  node *new_node = create(data, NULL);
  cursor->next = new_node;

  return head;
}

/*
 * Insert a new node after the previous node
 */
node *insert_after(node *head, int data, node *prev)
{
  node *cursor = head;

  // find the previous node
  while (cursor != prev)
    cursor = cursor->next;

  if (cursor != NULL) {
    node *new_node = create(data, cursor->next);
    cursor->next = new_node;
    return head;
  } else {
    return NULL;
  }
}

/*
 * Insert a new node before the next node
 */
node *insert_before(node *head, int data, node *next)
{
  if (next == NULL || head == NULL)
    return NULL;

  if (head == next) {
    head = prepend(head, data);
    return head;
  }

  node *cursor = head;

  while (cursor != NULL) {
    if (cursor->next == next)
      break;
    cursor = cursor->next;
  }

  if (cursor != NULL) {
    node *new_node = create(data, cursor->next);
    cursor->next = new_node;
    return head;
  } else {
    return NULL;
  }
}

/*
 * Call a function on each node in a list
 */
void traverse(node *head, callback fn)
{
  node *cursor = head;

  while (cursor != NULL) {
    fn(cursor);
    cursor = cursor->next;
  }
}

/*
 * Get the length of a linked list
 */
int count(node *head)
{
  node *cursor = head;
  int count = 0;

  while (cursor != NULL) {
    count++;
    cursor = cursor->next;
  }

  return count;
}

linkedlist.h

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_

#include <stdlib.h>

typedef struct node {
  int data;
  struct node *next;
} node;

typedef void (*callback)(node *data);

node *create(int data, node *next);

node *prepend(node *head, int data);

node *append(node *head, int data);

node *insert_after(node *head, int data, node *prev);

node *insert_before(node *head, int data, node *next);

void traverse(node *head, callback fn);

int count(node *head);

#endif

straight_mergesort.c

#include <stdio.h>
#include <stdlib.h>

#include "linkedlist.h"

node *straight_merge(node *head_a, node *head_b);
node *get_middle(node *head);

node *straight_mergesort(node *head)
{
  if (head == NULL || head->next == NULL)
    return head;

  // find the middle node and split the list
  node *middle = get_middle(head);
  node *second_half = middle->next;
  middle->next = NULL;

  return straight_merge(
    straight_mergesort(head),
    straight_mergesort(second_half)
  );
}

node *straight_merge(node *head_a, node *head_b)
{
  node *dummy_head = create(0, NULL);
  node *current = dummy_head;

  while (head_a != NULL && head_b != NULL) {
    if (head_a->data <= head_b->data) {
      current->next = head_a;
      head_a = head_a->next;
    } else {
      current->next = head_b;
      head_b = head_b->next;
    }
    current = current->next;
  }
  current->next = (head_a == NULL) ? head_b : head_a;
  return dummy_head->next;
}

node *get_middle(node *head)
{
  if (head == NULL)
    return head;

  node *slow = head;
  node *fast = head;
  while (fast->next != NULL && fast->next->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
  }

  return slow;
}

int main(void)
{
  node *head = create(2, create(1, create(4, create(3, NULL))));

  node *cursor = head;
  printf("Unsorted: ");
  while (cursor != NULL) {
    printf("%d -> ", cursor->data);
    cursor = cursor->next;
  }
  printf("NULL\n");

  head = straight_mergesort(head);

  cursor = head;
  printf("Sorted: ");
  while (cursor != NULL) {
    printf("%d -> ", cursor->data);
    cursor = cursor->next;
  }
  printf("NULL\n");
}

Compile:

$ gcc -o straight_mergesort straight_mergesort.c linkedlist.c

Run:

$ ./straight_mergesort
Unsorted: 2 -> 1 -> 4 -> 3 -> NULL
Sorted: 1 -> 2 -> 3 -> 4 -> NULL