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;
}

优化

使用哨兵位（dummy 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;
}

思路二

对原链表的节点指针进行修改，不消耗额外空间。使用三个指针 n1, n2, n3 进行迭代反转。

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;
}

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

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

题目要求判断给出的链表是否是一个回文结构，即前后对称。

思路一

将链表数据存入数组，使用左右指针向中间移动对比值。虽然题目要求空间复杂度 O(1)，但给定节点数不超过 900，定长数组视为常数空间。

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;
    }
};