Welcome to Rooeye's blog

有/无环单链表相关问题最优解

OJ rooeye 416℃ 0评论

1. 如何判断链表是否有环,如果有环返回入环节点

快指针,慢指针, 快指针每次走两步,慢指针每次走一步,如果二可以者相遇,则说明有环。当二者相遇的时候,将快指针重新指向头结点,然后快慢指针每次都走一步,相遇节点即为入环节点。

2.  无环单链表判断是否相交,相交返回第一个相交节点

                                             
设两个链表分别为 A,B, 长度分别为lenA,lenB,且lenA>lenB,首先A头指针headA先向前走(lenA-lenB)步,然后headA和headB同时向前走,每次走一步,如果二者没有相遇,说明链表未相交,如果二者相遇,相遇节点即为相交的第一个节点。

3.  有环单链表相交判断,如果二者相交,返回第一个相交节点。
两个有环单链表之间一共有三种状态。

(1)

(2)
(3)
需要考虑以上三种情况:
首先,得到两个有环链表各自的入环节点 , 设二者分别为A,B。如果A==B,说明为情况(3), 但是我们需要的是第一个相交节点,这时将入环节点看作终止节点,把问题转化为无环链表的相交问题。如果A!=B,说明为情况(1)或(2),这个时候从A开始遍历环,如果能在某个位置满足A==B,说明为情况(2),这个时候返回A和B之中的任意一个节点即可,反之为情况(1),二者不相交。

4. 单链表相交判断
这个时候得考虑有环无环两种情况,把上面所有情况综合考虑即可。





来自为知笔记(Wiz)

转载请注明:寻梦人博客 » 有/无环单链表相关问题最优解

喜欢 (1)
发表我的评论
取消评论

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址