算法面试——链表进阶：环形链表、复制随机指针链表

一、环形链表判断有环publicbooleanhasCycle(ListNodehead){ListNodeslowhead,fasthead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;if(slowfast)returntrue;}returnfalse;}二、环形链表II找环入口publicListNodedetectCycle(ListNodehead){ListNodeslowhead,fasthead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;if(slowfast){// 相遇后slow 从头开始fast 从相遇点继续slowhead;while(slow!fast){slowslow.next;fastfast.next;}returnslow;}}returnnull;}三、复制带随机指针的链表publicNodecopyRandomList(Nodehead){if(headnull)returnnull;MapNode,NodemapnewHashMap();Nodecurhead;while(cur!null){map.put(cur,newNode(cur.val));curcur.next;}curhead;while(cur!null){map.get(cur).nextmap.get(cur.next);map.get(cur).randommap.get(cur.random);curcur.next;}returnmap.get(head);} 觉得有用的话点赞 关注【张老师技术栈】吧