Linked List rearrangement Example 1

/* re-arrange nodes in the LL inplace as below
head : 1->2->3->4->5
output: 1->5->2->4->3
 */

#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
    int num;
    struct Node *next;
} Node;

Node *newNode(int num)
{
    Node *temp = (Node*) malloc(sizeof(Node));
    temp->num = num;
    temp->next = NULL;
    return temp;
}

void reverse (Node** head)
{
    Node *prev = NULL,  *cur = *head, *next;
    while(cur) {
    next = cur->next;
    cur->next = prev;
    prev = cur;
    cur = next;
    }
    *head = prev;
}

void reArrangeNodes( Node** head)
{
    Node *slow = *head;
    Node *fast = slow->next;
    // find the mid point
    while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    }
    Node *head1 = *head;
    Node *head2 = slow->next;
    slow->next = NULL;

    reverse(&head2);
    *head = newNode(0);
    Node* cur = *head;
    while(head1 || head2) {
    if (head1) {
        cur->next = head1;
        cur = cur->next;
        head1 = head1->next;
    }

    if (head2) {
        cur->next = head2;
        cur = cur->next;
        head2 = head2->next;
    }
    }
    *head = (*head)->next;
}
int main()
{
    Node *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
    head->next->next->next->next->next = newNode(6);
    head->next->next->next->next->next = newNode(7);
    printf("Input: ");
    Node *temp = head;
    while(temp) {
    printf ("%d ", temp->num);
    temp = temp->next;
    }
    printf("\n");
    reArrangeNodes(&head);
    printf("output: ");
    while(head) {
    printf("%d ", head->num);
    head=head->next;
    }
    printf("\n");
    return 0;
}