如何统计并列出circular doubly linked list中的所有mirror point

核心判定逻辑 #

镜像点的本质是：以该节点为起点，顺时针遍历全链表得到的序列，等于该节点为起点逆时针遍历全链表得到的序列，等价于该序列本身是回文序列。

具体实现步骤 #

• 第一步：先遍历一次链表，统计得到总节点数n。因为是循环链表，遍历终止条件为指针回到起点即可。
• 第二步：遍历链表的每一个节点作为候选镜像点，对每个候选节点做如下校验：
  1. 初始化两个遍历指针：fwd指向当前候选节点（负责顺时针遍历），bwd也指向当前候选节点（负责逆时针遍历）
  2. 共比对n次：每次先比对fwd->data和bwd->data，如果值不等，直接终止校验，当前节点不是镜像点；如果值相等，fwd = fwd->next顺时针走一步，bwd = bwd->prev逆时针走一步
  3. 如果n次比对全部相等，当前节点即为镜像点，存入结果列表即可。

可复用现有代码的改造点 #

你提供的遍历函数已经实现了正向、反向遍历的逻辑，只需要把原有打印值的逻辑替换为两个方向的值比对逻辑即可，不需要额外增加复杂操作。

参考代码片段 #

// 先实现统计链表长度的函数
int getLength(struct Node* start) {
    if(start == NULL) return 0;
    int len = 0;
    struct Node* temp = start;
    do {
        len++;
        temp = temp->next;
    } while(temp != start);
    return len;
}

// 判断单个节点是否为镜像点
int isMirrorPoint(struct Node* candidate, int n) {
    struct Node* fwd = candidate;
    struct Node* bwd = candidate;
    for(int i=0; i<n; i++) {
        if(fwd->data != bwd->data) {
            return 0;
        }
        fwd = fwd->next;
        bwd = bwd->prev;
    }
    return 1;
}

// 查找所有镜像点的主函数
void findAllMirrorPoints(struct Node* head) {
    if(head == NULL) {
        printf("空链表无镜像点");
        return;
    }
    int n = getLength(head);
    struct Node* temp = head;
    printf("所有镜像点的值为：");
    do {
        if(isMirrorPoint(temp, n)) {
            printf("%d ", temp->data);
        }
        temp = temp->next;
    } while(temp != head);
}

边界情况说明 #

• 空链表：无镜像点
• 仅1个节点的链表：该节点必然是镜像点
• 所有节点值相同的链表：所有节点都是镜像点

内容的提问来源于stack exchange，提问作者Ashwitha Banoth