链表常见操作：移除元素、合并、反转及回文判断

二、合并两个有序链表

题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/

题目描述与示例：

给定两个有序链表，要求合并成一个新的有序链表并返回头结点。

思路

类似于合并有序数组，使用双指针遍历两个链表，比较节点大小，将较小的节点尾插到新链表。当其中一个链表遍历结束时，将另一个链表的剩余节点直接连接到新链表尾部。需特殊处理空链表情况。

参考实现：

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;
    
    ListNode* pcur1 = list1;
    ListNode* pcur2 = list2;
    ListNode* newhead = NULL;
    ListNode* newtail = NULL;
    
    while (pcur1 && pcur2) {
        if (pcur1->val < pcur2->val) {
            if (newhead == NULL) {
                newhead = newtail = pcur1;
            } else {
                newtail->next = pcur1;
                newtail = pcur1;
            }
            pcur1 = pcur1->next;
        } else {
            if (newhead == NULL) {
                newhead = newtail = pcur2;
            } else {
                newtail->next = pcur2;
                newtail = pcur2;
            }
            pcur2 = pcur2->next;
        }
    }
    
    if (pcur1) newtail->next = pcur1;
    if (pcur2) newtail->next = pcur2;
    
    return newhead;
}