Java实现有环的单向链表,并判断单向链表是否有环
有一个单向链表,链表当中有可能出现环,就像下图这样。我们如何判断一个单向链表是否有环呢?
那么第一步,我们先实现一个这样的链表,接着再说如何判断这样的链表。
实现有环的单向链表
1、定义add(Node node)方法
/**
* 向链表末尾添加结点
*
* @param node 结点的next指向为null,表示尾结点。
* @return
*/
public boolean add(SingleNode node) {
if (first == null) {
first = node;
} else {
SingleNode last = get(getSize() - 1);
last.next = node;
}
size++;
return true;
}
/**
* 末尾添加一个特殊结点,形成一个环,为了测试用。
*
* @param node 这个node的next指向单项链表中已经存在的结点。
* @return
*/
public boolean addCycleNode(SingleNode node) {
if (getSize() < 2) {
return false;
}
SingleNode last = get(getSize() - 1);
last.next = node;
return true;
}
2、先正常生成一个无环的单向链表,最后在末尾添加一个结点,让该结点的next指向前面的某个结点。
// 循环链表
SingleLinkedList sll = new SingleLinkedList();
SingleNode head = new SingleNode(0, null);
sll.add(head);
for (int i = 1; i < 10; i++) {
SingleNode node = new SingleNode(i, null);
sll.add(node);
}
SingleNode sn = new SingleNode(111, null);
sll.add(sn);
for (int i = 10; i < 20; i++) {
SingleNode node = new SingleNode(i, null);
sll.add(node);
}
System.out.println(sll.toString());
输出如下:此时打印的还是一个无环单向链表。
SingleLinkedList:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 111, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
接着添加最后一个结点,让其next指向之前的sn结点,这样就形成了一个闭环。
// 最后一个结点的next指向之前添加的某个结点。
SingleNode last = new SingleNode(222, sn);
sll.add(last);
接着打印结果:需要注意的是,这里的打印log的方法我做了处理,具体细节请查看源码。
cycle:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 111, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 222, 111]
最后插入的结点的值为222,它的next指向的是111结点,如上所示,在222之后打印的就是111节点了,如果继续打印,就会一直循环打印下去。
判断单向链表是否有环
方法一:使用Hash Table
判断一个链表是否有环,我们只需要判断某个结点是否之前被访问过即可。这里我们优先想到的就是使用Hash表进行存储。
我们依次遍历访问每个结点,并将结点的引用存储到hash表中。如果当前结点是null,说明我们到达链表未尾部了,则当前链表一定无环;如果当前结点在hash表中已经存储过了,此时返回true即可。代码如下:
/**
* 判断单链表中是否有环
* 借助HashSet来判断。
*
* @param head
* @return
*/
public boolean hasCycleByHashSet(SingleNode head) {
Set<SingleNode> set = new HashSet<>();
SingleNode node = head;
while (node != null) {
if (set.contains(node)) {
return true;
} else {
set.add(node);
}
node = node.next;
}
return false;
}
方法二:使用快慢指针
首先创建两个指针1和2(在Java里就是两个对象引用),同时指向这个链表的头结点。然后开始一个大循环,在循环体中,1每次移动一个结点,2每次移动2个结点。最后比较这两个结点指向的结点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环。
代码如下:
/**
* 判断单链表中是否有环
* 借助快慢指针来判断。
*
* @param head
* @return
*/
public boolean hasCycleByTowPointers(SingleNode head) {
// 排除无数据或者只有一个数据且无闭环的情况
if (head == null || head.next == null){
return false;
}
SingleNode slow = head;
SingleNode fast = head.next;
while(slow != fast){
// 判断快指针结点是否为null,如果为null,则说明到达单向链表的结尾了。
if(fast == null || fast.next == null){
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
完整代码请查看
项目中搜索SingleLinkedList即可。
github传送门 https://github.com/tinyvampirepudge/DataStructureDemo
gitee传送门 https://gitee.com/tinytongtong/DataStructureDemo
参考:
1、linked-list-cycle