接外包,有相关需求的可以联系我:Telegram | Email

环形链表 | 快慢指针

该文章创建(更新)于02/18/2022,请注意文章的时效性!

Description

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

方法

快慢指针,如fast指针能遇到NULL则无法成环,当fast和slow相遇则说明成环。

CODE

这里最难搞得是理解ListNode的类

  • Python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:

        fast = head
        slow = head

        while(fast != None and slow != None):
            fast = fast.next.next
            slow = slow.next

            if fast == slow:
                return True

        return False
  • ListNode的理解

遍历主要要在创建前弄一个中间变量tmp(如下)来记录初始ListNode,环状则应该还需要单独记录一个cir(如下)来把最后的一个ListNode.next 指向这个ListNode。

# Definition for singly-linked list.
import time


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def hasCycle(self, head:ListNode):

        listN = ListNode(head[0])
        tmp = listN
        cir = listN
        # pos 为-1时则无环
        pos = -1
        for m in range(1, head.__len__()):
            listN.next = ListNode(head[m])
            listN = listN.next
            # 有环状的情况
            if m == pos:
                cir = listN
            print(listN.val)
            print('---------------')


        if cir.next != None:
            listN.next = cir

        fast = tmp
        slow = tmp

        while(fast != None and slow !=None):
            if(fast.next == None):
                return False
            fast = fast.next.next
            slow = slow.next

            if(fast == slow):
                return True

head = [3,2,0,-4]
S = Solution()
print(S.hasCycle(head))




print("___________________________________________________________________________________")





listN = ListNode(head[0])
# 中间变量,用来记录处理头listNode节点
tmp = listN
print(listN)
print(tmp)
print(listN.val)
print("#############################")
pos = 1
for m in range(1,head.__len__()):
    print("m\t" + str(m))
    listN.next = ListNode(head[m])
    listN = listN.next
    # 有环状的情况
    # 标记成环的地方
    if m == pos:
        cir = listN
    print(listN.val)
    print('---------------')

# 成环
try:
    if cir.next != None:
        listN.next = cir
    print('try')
except Exception as ex:
    print("Exception"+ex)

print(tmp)
print(listN)
print("#############################")
# while True:
#     print(listN.val)
#     if listN.next != None:
#         listN = listN.next
#         continue
#     else:
#         print(listN.next)

# 不能直接用ListN
# 因为上面一直在移动
# 建立一个中间的tmp来表示初始list
while tmp.next != None:
    print(tmp.val)
    print(tmp)
    tmp = tmp.next
    time.sleep(1)


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-
https://www.emperinter.info/2022/02/18/linked-list-cycle/


要不聊聊?

我相信你准备留下的内容是经过思考的!【勾选防爬虫,未勾选无法留言】

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码


阿里云国际版20美元
Vultr10美元
搬瓦工 | Bandwagon应该有折扣吧?
域名 | namesiloemperinter(1美元)