这是悦乐书的第176次更新,第178篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第35题(顺位题号是141)。给定一个链表,确定它是否有一个循环。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 理解题意

什么样结构的链表才算是拥有一个循环呢?

链表中某一节点的引用指向了当前链表中已经存在的另一节点时,此链表存在循环。

ListNode L = new ListNode(1);
ListNode L2 = new ListNode(2);
ListNode L3 = new ListNode(3);
ListNode L4 = new ListNode(4);
ListNode L5 = new ListNode(5);
ListNode L6 = new ListNode(6);
L.next = L2;
L2.next = L3;
L3.next = L4;
L4.next = L5;
L5.next = L3;

上面的链表就存在循环,L5的引用指向了L3。如果仅仅是节点值相等,是不存在循环的,因为他们的引用始终不同。

03 第一种解法

可以打个比方,如果两个人甲和乙同时在一条跑道上跑步,甲以2.5m/s的速度向前跑,乙以5m/s的速度向前跑,如果跑道是环形的,甲和乙肯定会在某一个地方至少相遇一次;如果跑道是直线形或非环形的,甲和乙是不会相遇的。

使用双指针,一个是正常向前,一次移动一个节点,第二个是间隔一个节点向前移动,如果第二个指针碰到了可以循环的节点,会在循环的过程中遇到第一个指针,此时就满足了形成循环的条件。

特殊情况:链表为空时,直接返回false。

public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode slow = head;
ListNode fast = head;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}

04 第二种解法

还是以上面跑步为例,不过稍微有点变化。甲还是以2.5m/s的速度跑步,此时乙在跑道中给了甲一根棒子,并站在原地等甲把棒子还给自己,如果跑道是环形的,乙肯定是会等到甲把棒子还给自己,如果跑道是直线或者非环形的,甲就带着棒子自己跑了。

我们可以使用一个标记,赋值给每一个节点,然后使用递归,直到碰到给出去的标志为止。

public boolean hasCycle2(ListNode head) {
if(head == null) {
return false;
}
if (head.val == Integer.MIN_VALUE-1) {
return true;
}
head.val = Integer.MIN_VALUE-1;
return hasCycle2(head.next);
}

如果某一个节点正好本身就拥有所要赋值的标志呢?会有一定影响,如果限制节点值的取值范围,此解法是完全可行的。

05 第三种解法

使用哈希表,将每一个节点的引用都存起来,如果哈希表中存在了某一个节点的引用,说明此链表是循环的。

public boolean hasCycle3(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}

此解法的空间复杂度是O(n)。

06 小结

笔试或者面试遇到此题时,推荐第一种解法,如果有限制链表节点值的取值范围,第二种解法也是完全可行的。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

05-06 16:53