判断单链表是否有环 + 找入环的第一个结点 + 找两个链表相交的起始结点
2021/9/18 23:05:47
本文主要是介绍判断单链表是否有环 + 找入环的第一个结点 + 找两个链表相交的起始结点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
- 给定一个链表,判断链表中是否有环
基本思想:采用快慢指针的思想,如果有环,快慢指针一定会相遇。
public boolean hasCycle(ListNode head) { //首先判断头结点 if(head == null){ return false; } ListNode fast = head; ListNode slow = head; while(fast!=null && fast.next!=null){ //用fast来遍历链表:如果没环,fast势必会有为空的时候 fast = fast.next.next; slow = slow.next; if(fast == slow){ return true; } } return false; }
- 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
public ListNode detectCycle(ListNode head) { if(head == null){ return null; } ListNode fast = head; ListNode slow = head; while(fast!=null && fast.next!=null){ //用fast来控制链表的遍历:如果没有环,fast势必会有为空的时候 fast = fast.next.next; slow = slow.next; if(fast == slow){ //快慢指针相遇:有环 //然后让一个指针从头开始走,另一个指针从相遇点开始走,两指针相遇的地方,就是环的入口 ListNode cur = head; while(cur != slow){ cur = cur.next; slow = slow.next; } return cur; } } return null; }
- 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA==null || headB==null){ return null; } ListNode pA = headA; ListNode pB = headB; int lenA = 0; int lenB = 0; while(pA != null){ lenA++; pA = pA.next; } while(pB != null){ lenB++; pB = pB.next; } int k = Math.abs(lenA-lenB); //让curA指向较长的链表 ListNode curA = headA; ListNode curB = headB; if(lenB > lenA){ curA = headB; curB = headA; } //让较长的链表先走差值步,然后两个链表同时走 while(k>0){ k--; curA = curA.next; } while(curA!=curB && curA!=null && curB!=null){ curA = curA.next; curB = curB.next; } //循环跳出的条件:有空或者相等 if(curA == curB){ return curA; } else{ return null; } }
这篇关于判断单链表是否有环 + 找入环的第一个结点 + 找两个链表相交的起始结点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?