用C语言完成以下链表4个典型应用的解题思路和代码撰写 1、链表原地逆置 2、求链表的中间(中左)结点 3、求链表的倒数第k个结点 4、2个有序链表的

1. **链表原地逆置**: 这个问题通常通过三个指针（两个快慢指针和一个反转指针）来解决。首先让快指针每次走两步，慢指针每次走一步，当快指针到达链表尾部时，慢指针的位置就是原链表的中间位置。然后从慢指针开始到头节点，依次将节点指向它的后继节点，实现了原地逆置。

void reverseList(struct Node** head) {
    struct Node* prev = NULL;
    struct Node* current = *head;
    struct Node* next = NULL;

    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    *head = prev;
}

2. **求链表的中间结点**: 可以借助双指针，一个移动速度快一倍，当快慢指针相遇时，慢指针所指的就是链表的中间结点。

struct Node* findMiddleNode(struct Node* head) {
    if (head == NULL || head->next == NULL)
        return head;
    struct Node* slow = head;
    struct Node* fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

3. **求链表的倒数第k个结点**: 这需要先找到链表的长度，然后从头节点开始向前移动k次。如果链表长度小于k，则返回NULL。

struct Node* kthFromEnd(struct Node* head, int k) {
    int length = countNodes(head);
    if (length < k)
        return NULL;
    Node* temp = head;
    for (int i = 0; i < length - k; i++)
        temp = temp->next;
    return temp;
}

int countNodes(struct Node* node) {
    if (node == NULL)
        return 0;
    return 1 + countNodes(node->next);
}

4. **2个有序链表合并**: 遇到相同值的情况下，可以优先选择第一个链表的节点。两个指针分别遍历两个链表，直到其中一个链表遍历完。

struct Node* mergeTwoLists(struct Node* l1, struct Node* l2) {
    struct Node* result = NULL, *temp = NULL;
    if (l1 == NULL)
        return l2;
    else if (l2 == NULL)
        return l1;
    
    if (l1->val <= l2->val) {
        result = l1;
        result->next = mergeTwoLists(l1->next, l2);
    } else {
        result = l2;
        result->next = mergeTwoLists(l1, l2->next);
    }
    
    return result;
}