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

一、移除链表元素

题目链接：https://leetcode.cn/problems/remove-linked-list-elements/

题目描述与示例：

根据题目描述，我们需要删除链表中值为指定值的节点，并返回新链表的头结点。

思路一

使用之前实现的链表方法，通过 Find 方法找到对应值，然后使用 Erase 方法删除，直到 Find 方法返回空指针结束。该方法实现简单，但效率较低。

思路二

本质与顺序表删除类似，使用双指针法。新建一个链表，遍历原链表，将非目标值的节点尾插到新链表。注意处理新链表头为空的情况，并在遍历结束后将新链表尾结点的 next 置为 NULL。

参考实现：

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    ListNode* newhead = NULL;
    ListNode* newtail = NULL;
    ListNode* pcur = head;
    while (pcur) {
        if (pcur->val != val) {
            if (newhead == NULL) {
                newhead = newtail = pcur;
            } else {
                newtail->next = pcur;
                newtail = pcur;
            }
        }
        pcur = pcur->next;
    }
    if (newtail) newtail->next = NULL;
    return newhead;
}

二、合并两个有序链表

题目链接：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;
}