昨天参加面试，要写链表反转和有序链表合并，一时居然没写出来，感觉太丢人了。

// test.h
#ifndef __TEST_INCLUDED_H__
#define __TEST_INCLUDED_H__

struct node;
typedef struct node *Node;

// 打印链表
void printList(Node head);
// 创建链表，并用数组参数给链表节点赋值
Node createList(int *arr, int n);
// 链表反转
Node reverseList(Node head);
// 有序链表拼接
Node append(Node head1, Node head2);
// 有序链表拼接
Node append1(Node head1, Node head2);
#endif

// test.c
struct node {
        int num;
        struct node *next;
};

// 打印链表
void printList(Node head)
{
        for (Node temp = head; temp; temp = temp->next)
                fprintf(stdout, "%d ", temp->num);
        puts("\n");
}

// 创建链表，并用数组参数中的值对元素进行初始化
Node createList(int *arr, int n)
{
        int i;
        Node head;

        head = calloc(n, sizeof(*head));
        if (head == NULL)
                return NULL;

        for (i = 0; i < n - 1; ++i) {
                head[i].num = arr[i];
                head[i].next = &head[i + 1];
        }
        // 给最后一个节点赋值
        head[i].num = arr[i];
        head[i].next = NULL;

        return head;
}

// 链表反转
Node reverseList(Node head)
{
        Node current, next, pre = NULL;

        for (current = head; current; current = next) {
                next = current->next;
                current->next = pre;
                pre = current;
                if (next == NULL)
                        break;
        }

        return current;
}

// 连接两个有序链表
Node append(Node head1, Node head2)
{
        int count;
        Node next;
        Node low = head1;
        Node high = head2;

        if (low->num > high->num) {
                low = head2;
                high = head1;
        }

        // 保存表头地址
        Node head = low;

        for (; low; low = next) {
                next = low->next;
                if (next == NULL) {
                        low->next = high;
                        break;
                }

                count = 0;
                Node pre;
                Node high_temp = high;
                while (high) {
                        if (high->num >= low->num && high->num < next->num) {
                                ++count;
                                pre = high;
                                high= high->next;
                        } else {
                                break;
                        }
                }
                // 需要插入节点
                if (count > 0) {
                        low->next = high_temp;
                        pre->next = next;
                }

                // 判断是否遍历完high链表
                if (high == NULL)
                        break;
        }

        return head;
}

Node append1(Node head1, Node head2)
{
        struct node node;
        Node current = &node;

        if (head1 == NULL)
                return head2;
        if (head2 == NULL)
                return head1;

        while (head1 && head2) {
                if (head1->num <= head2->num) {
                        current->next = head1;
                        head1 = head1->next;
                } else {
                        current->next = head2;
                        head2 = head2->next;
                }
                current = current->next;
        }

        return node.next;
}

// main.c
void test()
{
        int numbers[] = {12, 21, 34, 56, 78, 98, 102, 120, 245, 781, 889, 1203};
        int numbers1[] = {1, 8, 12, 89, 124, 245, 781, 809, 889, 1201, 1203, 8712};
        Node head = createList(numbers, ARRAYSIZE(numbers));
        printList(head);
        Node newHead = reverseList(head);
        printList(newHead);
        free(head);head = NULL;

        Node head1 = createList(numbers, ARRAYSIZE(numbers));
        Node head2 = createList(numbers1, ARRAYSIZE(numbers1));
        head = append(head1, head2);
        printList(head);
        free(head1);head1 = NULL;
        free(head2);head2 = NULL;

        head1 = createList(numbers, ARRAYSIZE(numbers));
        head2 = createList(numbers1, ARRAYSIZE(numbers1));
        head = append(head1, head2);
        printList(head);
        free(head1);head1 = NULL;
        free(head2);head2 = NULL;
}

int main(void)
{
        test();
        return 0;
}