LeetCode 链表经典题目解析：移除、反转、中间节点与回文结构

题目要求将两个有序链表合并成一个新的有序链表。

思路

使用双指针遍历两个链表，比较节点大小，将较小的节点尾插到新链表。当一个链表遍历完后，将另一个链表剩余部分直接接在新链表后。需特殊处理空链表情况。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;

    struct ListNode* pcur1 = list1, *pcur2 = list2;
    struct ListNode* newhead = NULL, *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;
}

优化

上述代码每次插入前都需判断链表是否为空。可以使用哨兵位（Sentinel Node）简化逻辑。申请一个不保存数据的头结点作为哨兵，直接在其后尾插，最后返回哨兵的下一个节点，记得释放哨兵位内存。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* pcur1 = list1, *pcur2 = list2;
    struct ListNode* guard = NULL, *tail = NULL;
    guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    tail->next = NULL;

    while (pcur1 && pcur2) {
        if (pcur1->val < pcur2->val) {
            tail->next = pcur1;
            tail = tail->next;
            pcur1 = pcur1->next;
        } else {
            tail->next = pcur2;
            tail = tail->next;
            pcur2 = pcur2->next;
        }
    }
    if (pcur1) tail->next = pcur1;
    if (pcur2) tail->next = pcur2;

    struct ListNode* head = guard->next;
    free(guard);
    return head;
}

三、反转链表

题目链接：反转链表

题目要求改变指针指向，使链表反转。

思路一

创建新链表，遍历原链表，使用头插法将节点插入新链表。

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head, *newhead = NULL;
    while (cur) {
        struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

思路二

修改原链表节点的指针指向，使用三个指针（prev, curr, next）依次反转，空间复杂度 O(1)。

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL) return head;
    struct ListNode* n1 = NULL, *n2 = head, *n3 = head->next;
    while (n2) {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3) n3 = n3->next;
    }
    return n1;
}

四、链表的中间节点

题目链接：链表的中间节点

返回链表的中间节点，若节点数为偶数，返回后一个中间节点。

思路一

先遍历统计节点总数 count，再遍历 count/2 次找到中间节点。

struct ListNode* middleNode(struct ListNode* head) {
    int count = 0;
    struct ListNode* pcur = head;
    while (pcur) {
        count++;
        pcur = pcur->next;
    }
    count /= 2;
    pcur = head;
    while (count--) {
        pcur = pcur->next;
    }
    return pcur;
}

思路二

使用快慢指针。快指针一次走两步，慢指针一次走一步。当快指针到达末尾时，慢指针即指向中间节点。

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* fast, *slow;
    fast = slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

五、综合应用之链表的回文结构

题目链接：链表的回文结构

判断链表是否前后对称。C++ 中可使用类封装。

思路一

将链表数据存入数组，使用左右双指针比较数组元素是否对称。虽然题目要求空间复杂度 O(1)，但给定节点数上限，定长数组可视为常数空间。

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        int arr[901] = {0};
        ListNode* pcur = A;
        int i = 0;
        while (pcur) {
            arr[i++] = pcur->val;
            pcur = pcur->next;
        }
        int left = 0, right = i - 1;
        while (left < right) {
            if (arr[left] != arr[right]) return false;
            left++, right--;
        }
        return true;
    }
};

思路二

利用之前的函数，先找中间节点，反转后半部分链表，然后与原前半部分比较。

class PalindromeList {
public:
    struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* cur = head, *newhead = NULL;
        while (cur) {
            struct ListNode* next = cur->next;
            cur->next = newhead;
            newhead = cur;
            cur = next;
        }
        return newhead;
    }

    struct ListNode* middleNode(struct ListNode* head) {
        struct ListNode* fast, *slow;
        fast = slow = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    bool chkPalindrome(ListNode* head) {
        struct ListNode* mid = middleNode(head);
        struct ListNode* rhead = reverseList(mid);
        while (head && rhead) {
            if (head->val != rhead->val) return false;
            head = head->next;
            rhead = rhead->next;
        }
        return true;
    }
};