基于自定义Java LinkedList类实现校验链表包含数组全部元素的方法遇到问题
代码现存问题梳理
语法层问题
Node类构造方法中this.value = value语句末尾缺失分号- if判断分支
if(tmp.value == arr[i)缺失右括号,无法通过编译
逻辑层问题
- 空指针风险:未做前置校验,若链表
head为null、输入数组长度大于0时,直接访问tmp.next会触发空指针异常;另外当匹配流程走到链表末尾节点后,指针会指向null,此时再访问tmp.next同样会触发空指针 - 遍历遗漏节点:循环条件使用
tmp.next != null,会跳过链表最后一个存储有效值的节点 - 匹配逻辑错位:当前代码对每个链表节点直接遍历整个数组做比对,未跟踪数组的匹配进度,只要当前节点值和数组某位置不相等就直接返回false,完全无法适配“链表包含全部数组元素”的判断目标。举个测试用例:链表为
1 -> 3 -> 2,目标数组为[1,2],实际链表是包含全部元素的,但原代码在比对到3节点时,因为和数组第二个元素2不匹配,会直接返回false,结果不符合预期。
正确实现参考
所有实现不依赖Java内置集合,完全基于给定的LinkedList结构编写,分两种最常见的判断场景给出方案:
场景1:要求数组元素按顺序、作为连续子序列完整出现在链表中
判断逻辑类似字符串的子串匹配,即从链表的每一个节点作为起始位置,向后逐节点和数组元素比对,只要能连续匹配完整个数组就返回true。
public boolean containsArray(int[] arr) { // 边界校验:空数组默认包含全部元素 if (arr.length == 0) return true; // 空链表无法包含非空数组 if (head == null) return false; Node start = head; // 遍历链表每一个节点作为匹配起点 while (start != null) { Node currNode = start; int matchIdx = 0; // 从当前起点开始,逐节点匹配数组元素 while (currNode != null && matchIdx < arr.length) { if (currNode.value == arr[matchIdx]) { matchIdx++; currNode = currNode.next; } else { break; } } // 连续匹配完整个数组,返回true if (matchIdx == arr.length) { return true; } start = start.next; } // 所有起点都尝试过没有匹配结果 return false; }
场景2:仅要求数组所有元素在链表中存在(不要求顺序、不要求连续,支持重复值计数匹配)
判断逻辑为:逐个遍历数组元素,对每个元素去链表中找未被标记过的匹配值,所有元素都能找到匹配就返回true。实现中通过临时移除已匹配节点的方式做标记,避免重复值重复计数。
public boolean containsArray(int[] arr) { if (arr.length == 0) return true; if (head == null) return false; // 逐个匹配数组中的每一个元素 for (int target : arr) { Node prev = null; Node curr = head; boolean found = false; // 在链表中查找当前目标值 while (curr != null) { if (curr.value == target) { // 找到匹配值,将该节点从链表中移除(标记为已使用),避免重复计数 if (prev == null) { head = curr.next; } else { prev.next = curr.next; } found = true; break; } prev = curr; curr = curr.next; } // 当前数组元素在链表中找不到可用匹配,直接返回false if (!found) return false; } // 所有数组元素都匹配完成 return true; }
注意:上述第二种场景的实现会修改原链表结构,如果需要保留原链表,可在开始匹配前先把链表节点的引用做备份,匹配完成后再还原结构即可。
内容的提问来源于stack exchange,提问作者h4ckerlinguist
相关产品推荐
相关产品推荐

