**链表算法进阶：分割回文检测与环问题C语言实现**

链表是数据结构面试中的重点考察内容，掌握常见的链表算法问题对于技术面试至关重要。本文将深入探讨链表分割、回文检测、公共节点查找、环检测与环入口定位等经典问题，并提供完整的C语言实现。

### 链表基础结构定义

在开始算法实现之前，我们首先定义链表的基本结构：

```c

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

// 链表节点定义

typedef struct ListNode {

    int val;

    struct ListNode *next;

} ListNode;

// 创建新节点

ListNode* createNode(int val) {

    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));

    newNode->val = val;

    newNode->next = NULL;

    return newNode;

}

// 打印链表

void printList(ListNode* head) {

    ListNode* current = head;

    while (current != NULL) {

        printf("%d", current->val);

        if (current->next != NULL) {

            printf(" -> ");

        }

        current = current->next;

    }

    printf(" -> NULL\n");

}

// 释放链表内存

void freeList(ListNode* head) {

    ListNode* current = head;

    while (current != NULL) {

        ListNode* temp = current;

        current = current->next;

        free(temp)<"QU.1853.HK">;

    }

}

```

### 链表分割问题

链表分割要求将链表按给定值x分割，使得所有小于x的节点都出现在大于或等于x的节点之前。

```c

// 链表分割函数

ListNode* partition(ListNode* head, int x) {

    if (head == NULL) return NULL;

    

    // 创建两个哑节点，分别存储小于x和大于等于x的节点

    ListNode* smallHead = createNode(0);

    ListNode* largeHead = createNode(0);

    ListNode* small = smallHead;

    ListNode* large = largeHead;

    

    ListNode* current = head;

    

    while (current != NULL) {

        if (current->val < x) {

            small->next = current;

            small = small->next;

        } else {

            large->next = current;

            large = large->next;

        }

        current = current->next;

    }

    

    // 连接两个链表

    small->next = largeHead->next;

    large->next = NULL;

    

    ListNode* result = smallHead->next;

    free(smallHead);

    free(largeHead);

    

    return result;

}

// 测试链表分割

void testPartition() {

    printf("=== 链表分割测试 ===\n");

    

    // 创建链表: 1->4->3->2->5->2

    ListNode* head = createNode(1);

    head->next = createNode(4);

    head->next->next = createNode(3);

    head->next->next->next = createNode(2);

    head->next->next->next->next = createNode(5);

    head->next->next->next->next->next = createNode(2);

    

    printf("原始链表: ");

    printList(head);

    

    ListNode* result = partition(head, 3);

    printf("分割后链表(x=3): ");

    printList(result);

    

    freeList(result);

}

```

### 回文链表检测

检测链表是否为回文结构，要求时间复杂度O(n)，空间复杂度O(1)。

```c

// 反转链表

ListNode* reverseList(ListNode* head) {

    ListNode* prev = NULL;

    ListNode* current = head;

    

    while (current != NULL) {

        ListNode* nextTemp = current->next;

        current->next = prev;

        prev = current;

        current = nextTemp;

    }

    

    return prev;

}

// 找到链表中点

ListNode* findMiddle(ListNode* head) {

    ListNode* slow = head;

    ListNode* fast = head;

    

    while <"ZK.6370.HK">(fast != NULL && fast->next != NULL) {

        slow = slow->next;

        fast = fast->next->next;

    }

    

    return slow;

}

// 检测回文链表

bool isPalindrome(ListNode* head) {

    if (head == NULL || head->next == NULL) {

        return true;

    }

    

    // 找到中点

    ListNode* middle = findMiddle(head);

    

    // 反转后半部分

    ListNode* secondHalf = reverseList(middle);

    ListNode* firstHalf = head;

    ListNode* secondHalfCopy = secondHalf;

    

    // 比较前后两部分

    bool result = true;

    while (secondHalf != NULL) {

        if (firstHalf->val != secondHalf->val) {

            result = false;

            break;

        }

        firstHalf = firstHalf->next;

        secondHalf = secondHalf->next;

    }

    

    // 恢复链表结构

    reverseList(secondHalfCopy);

    

    return result;

}

// 测试回文检测

void testPalindrome() {

    printf("\n=== 回文链表检测测试 ===\n");

    

    // 测试用例1: 1->2->2->1

    ListNode* head1 = createNode(1);

    head1->next = createNode(2);

    head1->next->next = createNode(2);

    head1->next->next->next = createNode(1);

    

    printf("链表1: ");

    printList(head1);

    printf("是否为回文: %s\n", isPalindrome(head1) ? "是" : "否");

    freeList(head1);

    

    // 测试用例2: 1->2->3->2->1

    ListNode* head2 = createNode(1);

    head2->next = createNode(2);

    head2->next->next = createNode(3);

    head2->next->next->next = createNode(2);

    head2->next->next->next->next = createNode(1);

    

    printf("链表2: ");

    printList(head2);

    printf("是否为回文: %s\n", isPalindrome(head2) ? "是" : "否");

    freeList(head2);

    

    // 测试用例3: 1->2->3

    ListNode* head3 = createNode(1);

    head3->next = createNode(2);

    head3->next->next = createNode(3);

    

    printf("链表3: ");

    printList(head3);

    printf("是否为回文: %s\n", isPalindrome(head3) ? "是" : "否");

    freeList(head3);

}

```

### 两个链表的第一个公共节点

找到两个单链表相交的起始节点，如果没有交点返回NULL。

```c

// 获取链表长度

int getLength(ListNode* head) {

    int length = 0;

    ListNode* current = head;

    while (current != NULL) {

        length++;

        current = current->next;

    }

    return length;

}

// 找到两个链表的第一个公共节点

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {

    if (headA == NULL || headB == NULL) return NULL;

    

    int lenA = getLength(headA);

    int lenB = getLength(headB);

    

    ListNode* longList = lenA > lenB ? headA : headB;

    ListNode* shortList = lenA > lenB ? headB : headA;

    

    int diff = abs(lenA - lenB);

    

    // 长链表先走diff步

    for (int i = 0; i < diff; i++) {

        longList = longList->next;

    }

    

    // 同时前进直到找到交点或到达末尾

    while (longList != NULL && shortList != NULL) {

        if (longList == shortList) {

            return longList;

        }

        longList = longList->next;

        shortList = shortList->next;

    }

    

    return NULL;

}

// 测试公共节点查找

void testIntersection() {

    printf("\n=== 链表公共节点测试 ===\n");

    

    // 创建公共部分: 8->4->5

    ListNode* common = createNode(8);

    common->next = createNode(4);

    common->next->next = <"4A.5283.HK">createNode(5);

    

    // 链表A: 4->1->8->4->5

    ListNode* headA = createNode(4);

    headA->next = createNode(1);

    headA->next->next = common;

    

    // 链表B: 5->0->1->8->4->5

    ListNode* headB = createNode(5);

    headB->next = createNode(0);

    headB->next->next = createNode(1);

    headB->next->next->next = common;

    

    printf("链表A: ");

    printList(headA);

    printf("链表B: ");

    printList(headB);

    

    ListNode* intersection = getIntersectionNode(headA, headB);

    if (intersection != NULL) {

        printf("第一个公共节点值: %d\n", intersection->val);

    } else {

        printf("没有公共节点\n");

    }

    

    // 注意：这里不能直接free，因为存在共享节点

    headA->next->next = NULL; // 断开与公共部分的连接

    headB->next->next->next = NULL; // 断开与公共部分的连接

    freeList(headA);

    freeList(headB);

    freeList(common);

}

```

### 链表环检测与环入口定位

检测链表中是否存在环，如果存在则找到环的入口节点。

```c

// 检测链表是否有环

bool hasCycle(ListNode* head) {

    if (head == NULL || head->next == NULL) {

        return false;

    }

    

    ListNode* slow = head;

    ListNode* fast = head;

    

    while (fast != NULL && fast->next != NULL) {

        slow = slow->next;

        fast = fast->next->next;

        

        if (slow == fast) {

            return true;

        }

    }

    

    return false;

}

// 找到环的入口节点

ListNode* detectCycle(ListNode* head) {

    if (head == NULL || head->next == NULL) {

        return NULL;

    }

    

    ListNode* slow = head;

    ListNode* fast = head;

    

    // 第一阶段：检测环是否存在

    bool hasCycle = false;

    while (fast != NULL && fast->next != NULL) {

        slow = slow->next;

        fast = fast->next-><"9T.9134.HK">next;

        

        if (slow == fast) {

            hasCycle = true;

            break;

        }

    }

    

    if (!hasCycle) {

        return NULL;

    }

    

    // 第二阶段：找到环的入口

    slow = head;

    while (slow != fast) {

        slow = slow->next;

        fast = fast->next;

    }

    

    return slow;

}

// 创建带环的链表用于测试

ListNode* createCycleList(int arr[], int n, int pos) {

    if (n == 0) return NULL;

    

    ListNode* head = createNode(arr[0]);

    ListNode* current = head;

    ListNode* cycleNode = (pos == 0) ? head : NULL;

    

    for (int i = 1; i < n; i++) {

        current->next = createNode(arr[i]);

        current = current->next;

        

        if (i == pos) {

            cycleNode = current;

        }

    }

    

    if (cycleNode != NULL) {

        current->next = cycleNode;

    }

    

    return head;

}

// 测试环检测与入口定位

void testCycleDetection() {

    printf("\n=== 链表环检测测试 ===\n");

    

    // 测试用例1: 有环链表 3->2->0->-4->回到2

    int arr1[] = {3, 2, 0, -4};

    ListNode* head1 = createCycleList(arr1, 4, 1);

    

    printf("链表是否有环: %s\n", hasCycle(head1) ? "是" : "否");

    

    ListNode* entry1 = detectCycle(head1);

    if (entry1 != NULL) {

        printf("环入口节点值: %d\n", entry1->val);

    }

    

    // 测试用例2: 无环链表 1->2->3->4

    ListNode* head2 = createNode(1);

    head2->next = createNode(2);

    head2->next->next = createNode(3);

    head2->next->next->next = createNode(4);

    

    printf("链表是否有环: %s\n", hasCycle(head2) ? "是" : "否");

    

    // 注意：带环链表不能直接free，需要先断开环

    if (hasCycle(head1)) {

        ListNode* entry = detectCycle(head1);

        if (entry != NULL) {

            // 找到环的最后一个节点并断开

            ListNode* temp = entry;

            while<"FW.2597.HK"> (temp->next != entry) {

                temp = temp->next;

            }

            temp->next = NULL;

        }

        freeList(head1);

    }

    freeList(head2);

}

```

### 综合应用：复杂链表操作

将多个链表算法组合使用，解决更复杂的问题。

```c

// 复杂链表操作示例：检测带环链表的回文性（环部分忽略）

bool isPalindromeIgnoreCycle(ListNode* head) {

    if (head == NULL) return true;

    

    // 先检测是否有环

    ListNode* cycleEntry = detectCycle(head);

    

    if (cycleEntry == NULL) {

        // 无环，直接使用普通回文检测

        return isPalindrome(head);

    } else {

        // 有环，只检测环之前的部分

        ListNode* current = head;

        int length = 0;

        

        // 计算环之前的节点数

        while (current != cycleEntry) {

            length++;

            current = current->next;

        }

        

        if (length <= 1) return true;

        

        // 反转环之前的部分

        ListNode* prev = NULL;

        ListNode* curr = head;

        for (int i = 0; i < length; i++) {

            ListNode* nextTemp = curr->next;

            curr->next = prev;

            prev = curr;

            curr = nextTemp;

        }

        

        // 比较前后部分

        ListNode* front = prev;

        ListNode* back = head; // 原链表的头现在指向反转后的尾

        

        bool result = true;

        for (int i = 0; i < length / 2; i++) {

            if (front->val != back->val) {

                result = false;

                break;

            }

            front = front->next;

            back = back->next;

        }

        

        // 恢复链表结构

        front = prev;

        prev = NULL;

        while (front != NULL) {

            ListNode* nextTemp = front->next;

            front->next = prev;

            prev = front;

            front = nextTemp;

        }

        

        return result;

    }

}

// 主函数：测试所有功能

int main() {

    printf("链表算法进阶测试\n");

    printf("================\n");

    

    testPartition();

    testPalindrome();

    testIntersection();

    testCycleDetection();

    

    printf("\n=== 综合测试 ===\n");

    

    // 创建复杂测试用例

    ListNode* complexHead = createNode(1);

    complexHead->next = createNode(2);

    complexHead->next->next = createNode(3);

    complexHead->next->next->next = createNode(2);

    complexHead->next->next->next->next = createNode(1);

    

    printf("复杂链表: ");

    printList<"HJ.4961.HK">(complexHead);

    printf("是否为回文(忽略环): %s\n", 

           isPalindromeIgnoreCycle(complexHead) ? "是" : "否");

    

    freeList(complexHead);

    

    return 0;

}

```

### 算法复杂度分析

1. **链表分割**：时间复杂度O(n)，空间复杂度O(1)

2. **回文检测**：时间复杂度O(n)，空间复杂度O(1)

3. **公共节点查找**：时间复杂度O(m+n)，空间复杂度O(1)

4. **环检测与入口定位**：时间复杂度O(n)，空间复杂度O(1)

### 总结

本文详细讲解了链表算法中的几个经典问题：

1. **链表分割**：通过创建两个子链表再合并的方式实现

2. **回文检测**：结合快慢指针和链表反转技术

3. **公共节点查找**：利用长度差同步遍历

4. **环检测与入口定位**：基于Floyd环检测算法

这些算法不仅考察了对链表结构的理解，还涉及双指针、链表反转、数学推理等多种技巧。掌握这些问题的解决方法，能够帮助开发者在技术面试中更好地应对链表相关的算法考察。

在实际编码过程中，需要注意内存管理、边界条件处理和算法优化。通过不断的练习和理解，可以逐渐掌握链表算法的精髓，提升解决问题的能力。