王道数据结构2.2.3——16、判断一个单链表是否为另一个单链表的连续子序列-白红宇的个人博客

王道数据结构2.2.3——16、判断一个单链表是否为另一个单链表的连续子序列

发布日期：2021-05-17 06:34:23 浏览次数：12 分类：精选文章

本文共 688 字，大约阅读时间需要 2 分钟。

思路

要同时遍历两个单链表A和B，可以采用双指针法。分别用两个指针ra和rb，分别指向A和B的下一个节点。

操作步骤如下：

如果ra和rb指针所指的节点数据不同，将ra指针移到其下一个节点，rb指针则回到链表起点。

如果ra和rb指针所指的节点数据相同，同时移动ra和rb指针各到下一个节点，继续比较。

此外，还要考虑链表长度的不一致情况。最终判断是否rb指针已经到达链表末尾。

代码

boolean findChild(LinkList A, LinkList B) {    LNode ra = A.next, rb = B.next, temp = A.next;    while (ra != null && rb != null) {        if (ra.data != rb.data) {              ra = temp.next;              temp = ra;            rb = B.next;        } else {            ra = ra.next;            rb = rb.next;        }    }    return rb == null;}

解释

代码逻辑首先将ra和rb分别初始化为A和B的下一个节点。通过while循环双向遍历两个链表：当两个节点数据不同时，ra被移到下一个节点，rb则归位到B的起点；当两个节点数据相同时，两个指针同时移动到下一个节点。最终，当某个链表遍历完毕时，函数返回true或false，表示是否成功找到目标节点。

上一篇：王道数据结构2.3.7——17、判断循环双链表是否对称

下一篇：王道数据结构2.3.7——15、两单链表的交集存放与其中一个单链表

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章