《数据结构》保姆级代码大题解析 —— 链表（上）

1. 在带头结点的单链表 L 中，删除所有值为 x 的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。

题目关键词：

带头结点：L本身是一个头结点，不存数据，L->next才指向第一个数据结点；

值为 x：目标是把所有data == x的结点从链中移除，free掉，且不能断链。

题目难点：

单链表删除结点的本质：让被删结点的前驱结点，直接指向被删结点的后继结点，否则链表会断链。因为单链表只有 next指针，无法直接找到前驱，所以必须额外记录前驱结点。

双指针法：

核心思路：p作为当前遍历的结点，pre作为p的前驱指针，q用作暂存结点，当p->data =  x              时，通过先用q来暂存要删除的结点，再pre->next = p->next来架空该结点，最后free彻底销毁掉，否则pre和p一块向后走。

bool Del_X_1(LinkList& L, ElemType x) {    LNode* p = L->next, * pre = L, * q;    //p指向第一个数据结点，pre是p的前驱结点    while (p != NULL) //遍历链表直到末尾    {        if (p->data == x)   //当前结点需要删除        {            q = p;          //q暂存要删除的结点，方便free            p = p->next;    //p先移到下一个结点，避免断链            pre->next = p;  //pre直接指向新的p，架空原p，把原p从链中移除            free(q);        //释放被删结点的空间        }        else //当前结点不需要删除        {            pre = p;        //pre移动到当前p            p = p->next;    //p移动到下一个结点        }    }    return true; }

边界情况处理：

链表为空时 (p == NULL)，直接返回，不执行循环。

第一个结点时x时，pre是头结点，pre->next = p->next直接让头结点指向第二个结点。

多个连续的x结点时，比如 x, x, 1, 2 第一次删除后p直接跳到下一个结点，pre不变，继续删除下一个x，不会漏删。

注意：

p先移动，再改pre->next：如果先改pre->next再移动p，会丢失p->next的地址，导致断链。

pre始终在p前面：pre 不会跳过任何结点，始终是p的直接前驱，所以删除时的链修改是安全的。

尾插法：

核心思路：p作为当前遍历的结点，r作为新链表的尾指针始终指向最后一个有效结点，q用作暂存结点，如果该结点需要保留时 (p->data != x)，直接把p接入新  链表              的尾部，如果当前结点需要删除时，直接用q暂存起来，然后通过next指针将其架空后free掉。

bool Del_X_2(LinkList& L, ElemType x) {    LNode* p = L->next, * r = L, * q;    //p指向原链表的第一个结点，r是新链的尾指针，初始指向头结点    while (p != NULL) //遍历原链表    {        if (p->data != x) //当前结点需要保留        {            r->next = p;  //把p接在新链的尾部            r = p;        //r移动到新的尾结点            p = p->next;  //p继续遍历原链表        }        else // 当前结点需要删除        {            q = p;          //暂存要删除的结点            p = p->next;    //p先移到下一个结点            free(q);        //释放被删结点        }    }    r->next = NULL; //遍历结束，把新链尾结点的next置空，防止残留指针    return true; }

边界情况处理：

如果待定链表的最后一个结点时x，则在free掉x后，r就指向了倒数第二个结点，而r->next依旧是指向已经被free掉的结点，会变成空指针，所以需要r->next = NULL;让其置空。

如果没有结点是需要删除的x，则运行到最后一步时存在r->next = NULL;也不会影响结果。

注意：

尾插法的本质：相当于 “过滤” 链表，把所有非x的结点按原顺序拼接起来，不需要额外的前驱指针。

2. 试编写在带头结点的单链表L中删除一个最小值结点的高效算法 (假设该结点唯一) 。

题目关键词：

带头结点：L是头结点，不存数据，L->next指向第一个数据结点；

最小值结点唯一：不需要处理多个相同最小值的情况，找到第一个即可；

高效算法：链表只能顺序遍历，所以最优时间复杂度是 O(n)，且只能遍历一次。

题目难点：

单链表删除结点的本质：让被删结点的前驱结点，直接指向被删结点的后继结点，否则链表会断链。因为单链表只有 next指针，无法直接找到前驱，所以必须额外记录前驱结点。

找最小值的同时，记录它的前驱：如果先遍历一遍找最小值，再遍历一遍找它的前驱，时间复杂度还是O (n)，但会多一次遍历，不够高效。题目要求的 “高效”，就是一次遍历同时完成找最小值和记录前驱。

核心思路：p作为当前遍历的结点，pre作为p的前驱指针，minp作为最小值结点，minpre作为最小值结点的前驱指针，且初始默认第一个结点就是minp；开始while循环比较，如果遇到的结点比之前定的minp还小，就更新minp值为当前结点值，且更新minpre为该最小值的前驱节点，如果没遇到更小的，pre和p同步后移；完全遍历完成后，先将最小值结点的前驱结点直接指向最小值结点的后继指针，以此来架空最小值结点，最后free掉它就好了。

LinkList Delete_Min(LinkList& L) {    LNode* pre = L, * p = pre->next;    LNode* minpre = pre, * minp = p;    //遍历链表所有结点    while (p != NULL)    {        //如果当前结点p的数据比当前最小值还小        if (p->data < minp->data)        {            //更新最小值结点和它的前驱            minp = p;            minpre = pre;        }        //pre和p一起向后移动，继续遍历        pre = p;        p = p->next;    }    //找到最小值结点后，执行删除操作    minpre->next = minp->next; //最小值结点的前驱直接指向最小值结点的后继，架空最小值结点    free(minp);                //释放最小值结点的空间    return L; }

注意：

一次遍历双任务：遍历的本质是同时完成 “找最小值结点” 和 “记录它的前驱结点”，避免了 “先找最小值、再找前驱” 的两次遍历，保证了算法的高效性。

边界情况处理：①如果链表为空，需要先判断L->next == NULL，否则minp为NULL，访问minp->data会导致空指针访问错误；②如果最小值结点是链表的第一个结点，此时minpre指向头结点，删除操作minpre->next = minp->next会让头结点直接指向第二个结点，逻辑依然成立，无需额外分支处理；③如果最小值结点是链表的最后一个结点，删除后minpre->next会被置为NULL，避免野指针问题。

3. 试编写算法将带头结点的单链表就地逆置，所谓"就地”是指辅助空间复杂度为 O (1) 。

题目关键词：

带头结点：L为头结点，不存数据，L->next指向第一个数据结点。

就地逆置：不能额外开辟新链表，只能在原链表上修改指针指向。

空间复杂度 O (1)：只能使用常数个额外指针，不能用数组 / 栈等额外存储结构。

题目难点：

单链表逆置的本质是把每个结点的 next 指针指向它的前驱结点，但单链表本身无法直接访问前驱，所以需要用额外指针记录前驱 / 后继，同时要避免断链导致后续结点丢失。

头插法逆置：

核心思路：

初始化一个空链表，把原链表的结点依次用头插法插入，原链表的尾结点会变成新链表的头结点，实现逆置。

LinkList Reverse_1(LinkList L) {    LNode* p, * r;    p = L->next;  //p指向原链表的第一个数据结点    L->next = NULL; //头结点的next置空，相当于初始化一个空的新链表    while (p != NULL) //遍历原链表所有结点    {        r = p->next;   //暂存p的下一个结点，防止断链        p->next = L->next; //把p插入到头结点的后面（头插）        L->next = p;   //头结点指向新的第一个结点p        p = r;         //p回到原链表的下一个结点，继续处理    }    return L; }

边界情况处理：

链表为空 (L->next == NULL)：该算法的循环不执行，直接返回头结点；

链表只有一个数据结点：Reverse_1: 循环执行一次，头插后链表不变；

链表有多个结点：该算法都能正确遍历并反转，不会断链。

三指针逆置：

核心思路：

用三个指针依次遍历，让每个结点的next指针指向它的前驱结点，最后更新头结点指向原链表的尾结点，完成逆置。

LinkList Reverse_2(LinkList L) {    LNode* pre, * p = L->next, * r = p->next;    p->next = NULL; //第一个数据结点变成逆置后的尾结点，next置空    while (r != NULL) //遍历到最后一个结点    {        pre = p;      //pre记录当前结点p，作为下一个结点的前驱        p = r;        //p移动到下一个结点r        r = r->next;  //r再移动到下下个结点        p->next = pre; //把p的next指向前驱pre，完成反转    }    L->next = p; //循环结束时p指向原链表的最后一个结点，即新链表的头结点    return L; }

边界情况处理：

链表为空 (L->next == NULL)：该算法的循环不执行，直接返回头结点；

链表只有一个数据结点：Reverse_2: r = p->next为NULL，循环不执行，L->next = p；

链表有多个结点：该算法都能正确遍历并反转，不会断链。

注意：

头插法需初始化L->next = NULL，避免新链表残留指针。

三指针法需将首结点next置空，循环结束后更新头结点指向原尾结点。

空链表、单结点链表需单独考虑边界逻辑，避免空指针访问错误。

遍历过程中必须暂存后继结点，防止断链。

4. 设在一个带表头结点的单链表中，所有结点的元素值无序，试编写一个函数，删除表中所有处于给定的两个值 (作为函数参数给出) 之间的元素 (若存在) 。

题目关键词：

无序：链表元素值无序，可能存在多个满足条件的结点。

题目难点：

单链表删除结点的本质：让被删结点的前驱结点，直接指向被删结点的后继结点，否则链表会断链。因为单链表只有 next指针，无法直接找到前驱，所以必须额外记录前驱结点。

核心思路：采用前驱指针pr与当前指针p(初始为第一个  数据              结点) 同步遍历链表，循环判断每个结点是否处于区间(min, max)内，若满足条件，则通过前驱结点直接跳过该结点并释放空间，当前指针p直接指向新的后继结点；若不满足条件，则两个指针同步后移，完成遍历。

void RangeDelete(LinkList& L, int min, int max) {    LNode* pr = L, * p = L->link;    while (p != NULL) //遍历链表所有结点    {        //判断当前结点是否在(min, max)区间内        if (p->data > min && p->data < max)        {            //让前驱结点 pr 的指针直接指向 p 的后继结点，跳过 p            pr->link = p->link;            //释放被删结点的空间            free(p);            //p移动到新的下一个结点            p = pr->link;        }        else        {            //当前结点不需要删除，前驱和当前结点同步向后移动            pr = p;            p = p->link;        }    } }

边界情况处理：

链表为空：L->link == NULL，循环不执行，函数直接结束，无错误；

所有结点都在区间内：遍历过程中所有结点都会被删除，最终pr停留在头结点，p变为NULL，链表变为空表；

无结点在区间内：pr和p同步遍历，链表不发生任何修改，逻辑正常；

连续多个结点在区间内：删除第一个满足条件的结点后，p直接指向后续结点，无需移动pr，不会漏删；

第一个结点在区间内：pr为头结点，pr->link = p->link直接让头结点指向第二个结点，删除成功；

最后一个结点在区间内：删除后pr->link变为NULL，链表尾指针正确置空，无野指针问题。

注意：

必须使用前驱指针pr，保证删除操作不断链。

删除结点后，p直接指向后继结点，pr不移动，可处理连续删除场景。

需判断空链表，防止空指针访问。

区间判断条件为min < data < max，不要写错逻辑。

删除结点后必须执行free释放空间。

5. 设 C = {a1,b1,a2,b2,···,an,bn} 为线性表，采用带头结点的单链表存放，设计一个就地算法，将其拆分为两个线性表，使得 A = {a1,a2,···,an}，B = {bm,···,b2,b1} 。

题目关键词：

A = {a1, a2, …, an} (原链表中所有奇数位的结点，保持原序)

B = {bn, …, b2, b1} (原链表中所有偶数位的结点，逆序存放)

就地算法：不额外开辟结点空间，仅修改指针，辅助空间复杂度为 O (1)。

题目难点：

同时处理两个链表：遍历原链表时，要同时把奇数位结点尾插到A，偶数位结点头插到B，保证原链表不断链。

偶数位结点逆序：头插法天然实现逆序，无需额外反转操作。

就地性：所有结点直接从原链表摘下复用，不malloc新结点。

核心思路：p作为当前遍历的结点 (初始为第一个结点)，q用作暂存结点，构建A链表 (用ra作为尾指针，每次直接将当前结点p尾插到A链表，尾插后ra和p同步向后走，ra始终指向A链表的尾戒点)，构建B链表 (每次将当前偶数位的结点p头插到B链表中，头插天然逆序)，遍历结束后A链表尾指针置空。

LinkList DisCreat_2(LinkList& A) {    LinkList B = (LinkList)malloc(sizeof(LNode));    B->next = NULL;  //为B创建一个头结点    LNode* p = A->next, * q;    LNode* ra = A;    while (p != NULL)    {        //处理奇数位结点：尾插到A链表        ra->next = p;   //把p接在A的尾部        ra = p;         //ra移动到新的尾结点        p = p->next;    //p移动到下一个结点 (即下一个偶数位结点)        //处理偶数位结点：头插到B链表        if (p != NULL)        {            q = p->next;       //暂存p的后继结点，防止断链            p->next = B->next; //把p头插到B的头部            B->next = p;       //B的头结点指向新的第一个结点p            p = q;             //p回到原链表的下一个结点，继续遍历        }    }    //遍历结束，将A链表的尾结点next置空，防止残留指针    ra->next = NULL;    return B; }

边界情况处理：

原链表为空（A->next == NULL）：循环不执行，A链表为空链表，B链表也为空链表，逻辑正常。

原链表只有奇数个结点（最后一个是 an）：循环中p != NULL条件不成立，最后一个结点仅尾插到 A，B 的结点数比 A 少 1，逻辑正常。

原链表只有两个结点（a1,b1）：a1尾插到A链表，b1头插到B链表，最终A={a1}, B={b1}，逻辑正常。

原链表结点数为偶数：所有结点都被处理，A链表和B链表的结点数相等，B链表天然逆序，逻辑正常。

注意：

必须用q暂存偶数位结点的后继，防止断链。

遍历结束后需将ra->next置空，避免野指针。

偶数位结点必须用头插法，才能天然实现逆序。

处理奇数个结点的链表时，最后一个结点仅加入A，无需额外处理。

需为B创建头结点，保持链表结构统一。

6. 在一个递增有序的单链表中，存在重复的元素。设计算法删除重复的元素，例如(7,10,10,21,30,42,42,42,51,70) 将为 (7,10,21,30,42,51,70)。

题目难点：

链表有序，重复元素必然连续，无需额外遍历查找重复值。

删除结点时需保证链表不断链，且释放被删结点空间。

利用 “有序” 特性，仅需一次遍历即可完成去重，时间复杂度 O (n)。

核心思路：p作为当前遍历的结点 (初始为第一个结点)，q用作暂存结点，循环判断p->data和p->next->data大小，相等时通过架空操作删除后继结点，不相等时p 向后移动，直到检查到最后一个结点停止。

void Del_Same(LinkList& L) {    //p指向第一个数据结点，作为当前“基准结点”    LNode* p = L->next, * q;    //处理空链表边界    if (p == NULL)        return;    //只要p的下一个结点不为空，就继续检查    while (p->next != NULL)    {        //q指向p的下一个结点，即待检查的结点        q = p->next;        if (p->data == q->data) //结点值重复，删除q        {            p->next = q->next; //p直接指向q的后继，跳过q            free(q);           //释放被删结点的空间        }        else        {            //结点值不重复，p向后移动，继续检查下一组            p = p->next;        }    } }

边界情况处理：

空链表：L->next == NULL，函数直接返回，无错误。

链表只有一个结点：p->next == NULL，循环不执行，链表保持不变。

所有结点值都相同：如(10,10,10)，循环会依次删除后两个结点，最终链表只剩一个10。

无重复结点：p会遍历整个链表，不执行删除操作，链表保持不变。

连续多个重复结点：如(42,42,42)，第一次删除第二个 42 后，p仍指向第一个 42，继续检查新的后继结点，删除第三个 42，处理正确。

注意：

必须先判断空链表，防止p为NULL导致空指针访问。

删除重复结点时，p不能移动，否则会漏删后续连续重复结点。

循环条件为p->next != NULL，避免访问空指针的data。

被删结点必须用free释放，防止内存泄漏。

仅适用于有序链表，无序链表无法直接用此方法去重。

7. 设A和B是两个单链表 (带头结点) ，其中元素递增有序。设计一个算法从 A 和 B 中的公共元素产生单链表 C，要求不破坏 A、B 的结点。

题目难点：

两个链表均为有序，可利用有序特性进行高效双指针遍历，避免暴力匹配。

不破坏A、B结点，意味着C链表的结点需要单独malloc创建，不能直接复用A、B的结点。

需正确维护C链表的尾指针，保证新结点尾插时链表不断链。

核心思路：p指向A链表的第一个数据结点，q指向B链表的第一个数据结点，r作为C链表的尾指针，初始指向头结点，p和q分别同时遍历两个链表，当p->data < q->data时说明当前p的值不存在于B链表中，直接继续向后移动p，当p->data > q->data时说明当前q的值不存在于A链表中，直接继续向后移动q，当p->data = q->data时找到了公共元素，此时创建新结点  s              并尾插到C链表，之后继续同时遍历p、q指针，直到遍历结束，将C链表尾指针置空。

void Get_Common(LinkList A, LinkList B) {    LNode* p = A->next, * q = B->next, * r, * s;    LinkList C = (LinkList)malloc(sizeof(LNode));    r = C;    //双指针遍历，只要p和q都不为空就继续比较    while (p != NULL && q != NULL)    {        if (p->data < q->data)        {            //A当前值较小，向后移动p            p = p->next;        }        else if(p->data > q->data)        {            //B当前值较小，向后移动q            q = q->next;        }        else        {            //找到公共元素，创建新结点s            s = (LNode*)malloc(sizeof(LNode));            s->data = p->data;            //将s尾插到C链表            r->next = s;            r = s;            //两个指针同时向后移动            p = p->next;            q = q->next;        }    }    //遍历结束，将C的尾结点next置空，防止野指针    r->next = NULL; }

边界情况处理：

A 或 B 为空链表：while条件不成立，C 仅含头结点，无数据结点，逻辑正常。

A 和 B 无公共元素：遍历结束后 C 仅含头结点，无数据结点，逻辑正常。

A 和 B 有连续多个公共元素：双指针会依次匹配所有公共元素，逐个创建结点加入 C，逻辑正常。

公共元素在链表尾部：双指针遍历到尾部时匹配成功，创建结点加入 C，逻辑正常。

注意：

双指针遍历条件为p != NULL && q != NULL，避免空指针访问。

公共元素结点需单独malloc创建，不可直接复用 A、B 的结点。

C 链表的尾指针r需及时更新，遍历结束后需置空r->next。

原链表A、B的指针仅移动不修改，保证不破坏原结构。

需处理A或B为空链表的边界情况。

8. 已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。编制函数，求A与B的交集，并存放于 A 链表中。

题目难点：

有序链表交集的高效求法：利用两个链表的递增有序特性，采用双指针同步遍历，时间复杂度为O(len(A) + len(B))，无需暴力匹配。

就地修改A链表：直接复用A链表中属于交集的结点，删除不属于交集的结点，不额外开辟新结点。

内存管理：必须释放A中不属于交集的结点、B链表的所有结点，避免内存泄漏。

核心思路：pa、pb分别作为遍历A链表、B链表的结点，pc作为C链表(结果链表)的尾指针，分别用pa、pb遍历A、B链表，当pa->data == pb->data时找到交集，将pa存入  pc              中，并释放pb；当pa->data < pb->data时说明pa在B链表中不存在，删除释放pa；当pa->data > pb->data时说明pb在A链表中不存在，删除释放pb。遍历结束后，分别释放A、B链表中的所有结点，将尾指针置空，最后释放B链表的头结点。，

LinkList Link_Union(LinkList& la, LinkList& lb) {    LNode* pa = la->next, * pb = lb->next;    LNode* u, * pc = la;    //双指针同步遍历，只要pa和pb都不为空就继续比较    while (pa && pb)    {        if (pa->data == pb->data)        {            //找到交集元素，将pa结点链入结果部分            pc->next = pa;            pc = pa;        //更新尾指针            pa = pa->next;  //pa后移            //释放B中当前匹配的结点            u = pb;            pb = pb->next;            free(u);        }        else if (pa->data < pb->data)        {            //A当前元素较小，不属于交集，直接删除            u = pa;            pa = pa->next;            free(u);        }        else        {            //B当前元素较小，不属于交集，直接删除            u = pb;            pb = pb->next;            free(u);        }    }    //释放A中剩余的结点 (不再有B中元素可匹配)    while (pa)    {        u = pa;        pa = pa->next;        free(u);    }    //释放B中剩余的结点 (不再有A中元素可匹配)    while (pb)    {        u = pb;        pb = pb->next;        free(u);    }    //结果链表的尾结点next置空，防止野指针    pc->next = NULL;    //释放 B 的头结点    free(lb);    return la; }

边界情况处理：

A 或 B 为空链表：双指针循环不执行，直接释放所有结点，结果链表A仅含头结点。

A 和 B 无交集元素：双指针遍历过程中，pa和pb会被全部删除，结果链表A仅含头结点。

A 和 B 完全相同：所有元素都属于交集，结果链表为原A，同时释放B的所有结点。

交集元素在链表尾部：双指针会遍历到尾部，匹配成功后链入结果链表，处理正确。

注意：

双指针遍历条件为pa && pb，避免空指针访问。

结果链表尾指针pc需及时更新，遍历结束后必须置空pc->next。

所有不属于交集的结点 (包括A、B的剩余结点) 都要释放，最后释放B的头结点。

交集结点需复用A的结点，不可创建新结点，以实现就地修改。

需处理A或B为空链表的边界情况。

9. 两个整数序列 A=a1,a2,a3,···,am 和 B=b1,b2,b3,···,bn 已经存入两个单链表中，设计一个算法，判断序列 B 是否是序列 A 的连续子序列。

题目关键词：

判断序列 B 是否是序列 A 的连续子序列：B的元素需按顺序、连续地出现在A中，不能跳位，且顺序必须一致。

题目难点：

需要在A中找到匹配B的起始位置，匹配失败时要回退到下一个起始位置重新匹配。

单链表无法随机访问，只能通过指针顺序遍历和回退。

需正确处理边界情况，如B比A长、链表为空等。

核心思路：p、q作为A、B链表中遍历的结点，pre记录 A 中每次匹配的起始位置，匹配失败时，A 的指针回退到pre->next重新开始。p、q开始遍历链表，当p->data == q->data时，匹配成功，p、q同时后移，匹配失败时A的起始位置后移一位，B的指针重置，重新开始匹配。遍历结束后，若q == NULL，说明B的所有元素都已匹配完成，B是A的连续子序列，返回1；若p == NULL而q != NULL，说明A已遍历完但B未匹配完，B不是A的连续子序列，返回0。

int Pattern(LinkList A, LinkList B) {    LNode* p = A;    LNode* pre = p;    LNode* q = B;    //当A和B都没遍历完时，继续匹配    while (p && q)    {        if (p->data == q->data)    {            //当前元素匹配成功，两个指针同时后移            p = p->next;            q = q->next;        }        else        {            //匹配失败，A从下一个位置重新开始，B回到开头            pre = pre->next;            p = pre;            q = B;        }    }    //如果B遍历完了，说明匹配成功；否则失败    if (q == NULL)        return 1;    else        return 0; }

边界情况处理：

A 或 B 为空链表：若B为空，按题目语义可视为匹配成功；若A为空且B不为空，匹配失败。

B 比 A 长：A遍历完时B未匹配完，直接返回0。

B 与 A 完全相同：匹配一次成功，B遍历完后返回1。

B 在 A 的尾部匹配成功：A和B同时遍历完，返回1。

B 在 A 中多次部分匹配但最终失败：如A={1,2,3,4}，B={1,3}，会先匹配1，然后在2处失败，再从2开始匹配，最终返回0。

注意：

pre指针需正确记录每次匹配的起始位置，匹配失败时回退。

B 的指针每次匹配失败时需重置到开头，否则无法重新匹配。

循环条件为p && q，避免空指针访问。

需处理 B 比 A 长、链表为空的边界情况。

结果判断需以q == NULL为标准，不能以p的状态判断。

10. 设计一个算法用于判断带头结点的循环双链表是否对称。

题目关键词：

带头结点的循环双链表：链表首尾相连，每个结点有next和prior指针，头结点的next指向第一个数据结点，prior指向最后一个数据结点。

判断是否对称：链表正序和逆序读取的结点值序列完全相同，即a1 = an, a2 = a(n-1), ...。

题目难点：

循环双链表首尾相连，需正确找到链表的第一个和最后一个数据结点。

利用双指针从两端向中间同步遍历，同时判断对称位置的结点值是否相等。

需正确处理循环双链表的终止条件，避免无限循环。

核心思路：p从链表头结点的next出发，指向第一个数据结点(L->next)、q从链表头结点的prior出发，指向最后一个数据结点(L->prior)。p、q同时开始向中间遍历，若对称位置相同则p、q同时向中间走一步，若对称位置不同就直接返回0咯，全部判断完成后都相同的话，就返回1。

int Symmetry(DLinkList L) {    DNode* p = L->next, * q = L->prior;    //循环条件：p和q未相遇(奇数个结点)，也未相邻(偶数个结点)    while (p != q && p->next != q)    {        if (p->data == q->data)        {            //对称位置值相等，p向后走，q向前走            p = p->next;            q = q->prior;        }        else        {            //对称位置值不等，链表不对称，直接返回0            return 0;        }    }    //所有对称位置都匹配，链表对称，返回1    return 1; }

边界情况处理：

空链表：L->next == L且L->prior == L，循环条件不成立，直接返回1(空链表视为对称)。

只有一个数据结点：p和q都指向该结点，循环条件不成立，直接返回 1。

两个数据结点：p->next == q，循环条件不成立，直接返回1 (只要两个结点值相等即对称，此处无需额外判断，也可补充判断p->data == q->data\) 。

奇数个结点：指针最终在中间结点相遇，循环结束，所有对称结点已匹配。

偶数个结点：指针最终走到中间两个相邻结点，循环结束，所有对称结点已匹配。

注意：

p和q必须分别初始化为L->next和L->prior，正确定位首尾数据结点。

循环条件需同时包含p != q和p->next != q，避免奇数 / 偶数结点时的死循环。

空链表、单结点链表、双结点链表的边界情况需处理。

每次比较不相等时直接返回0，无需继续遍历。