面试中算法(链表）

今天药忘吃喽~ 2024-05-28 10:21 50阅读 0赞

## 链表相关的题 ##

有一个单向链表，链表中有可能出现“环”，如图所示，如何用程序来判断该链表是否为有环链表呢?

![ace878220fe946cfabf21073627a7d9f.png][]

对于这道题，有一个很巧妙的方法，这个方法利用了两个指针。

首先创建两个指针pi和p2(在Python里就是两个对象引用)，让它们同时指向这个链表的头节点。然后开始循环，在循环体中，**让指针p1每次向后移动1个节点，让指针p2每次向后移动2个节点，然后比较两个指针指向的节点是否相同。如果相同，则可以判断出链表有环，如果不同，则继续下一次循环。**

**第1步，p1和p2都指向节点10**

![496a1994313840f693c0e3c025116397.png][]

**第2步，p1指向节点9，p2指向节点5**

![cc8265526db1470188d173bf7de3306f.png][]

**第3步，p1指向节点5，p2指向节点6**

![0625f565b9ad4e4ba60fd9d75fb77812.png][]

**第4步，p1指向节点2，p2指向节点3**

![5f6e17276d024eccbab152e7872bb303.png][]

**第5步，p1指向节点6，p2也指向节点6，p1和p2所指相同，说明链表有环。**

![20954e6425d24465bf87b95682f8fc48.png][]

> 这个题类似于数学上的追及问题。在一个环形跑道上，两个运动员从同一地点起跑，一个运动员速度快，另一个运动员速度慢。当两人跑了一段时间后，速度快的运动员必然会再次追上并超过速度慢的运动员，原因很简单，因为跑道是环形的。

如果链表的节点数量为n，则该算法的**时间复杂度为O (n)**。除两个指针外，没有使用任何额外的存储空间，所以**空间复杂度是O（1)。**

class MyNode:
        '''初始化节点'''
        def __init__(self,data):
            self.data=data
            self.next=None
    
    def circle_linked(head):
        #p1,p2指针指向第一个
        p1=p2=head
        #循环判断
        while p1 is not None and p2.next is not None:
            #指针p1每次向后移动1个节点
            p1=p1.next
            #指针p2每次向后移动2个节点，
            p2=p2.next.next
            #判断如果相同，返回True
            if p1==p2:
                return True
    
        return False
    
    
    if __name__ == '__main__':
         #节点数据
         n1=MyNode(10)
         n2=MyNode(9)
         n3=MyNode(5)
         n4=MyNode(2)
         n5=MyNode(6)
         n6=MyNode(8)
         n7=MyNode(3)
         #链表
         n1.next=n2
         n2.next=n3
         n3.next=n4
         n4.next=n5
         n5.next=n6
         n6.next=n7
         n7.next=n4
    
         #调方法
         print(circle_linked(n1))

> 扩展问题1: 如果链表有环，如何求出环的长度?
> 
>  当两个指针首次相遇，证明链表有环的时候，让两个指针从相遇点继续循环前进，并统计前进的循环次数，直到两个指针第2次相遇。此时，统计出来的前进次数就是环长。
> 
> **环长=每一次速度差×前进次数**

class MyNode:
        def __init__(self, data):
            self.data = data
            self.next = None
    
    
    def hasCycle(head):
        # p1,p2指针指向第一个
        p1 = p2 = head
        #环长
        len = 0
        # 循环判断
        while p1 is not None and p2.next is not None:
            # 指针p1每次向后移动1个节点
            p1 = p1.next
            # 指针p2每次向后移动2个节点，
            p2 = p2.next.next
            # 判断如果相遇，就结束循环
            if p1 == p2:
                break
        #循环判断
        while (p2 != None) & (p2.next != None):
            p1 = p1.next
            p2 = p2.next.next
            len = len + 1
            if p1 == p2:
                break
    
        return len
    
    
    if __name__ == '__main__':
         #节点数据
         n1=MyNode(10)
         n2=MyNode(9)
         n3=MyNode(5)
         n4=MyNode(2)
         n5=MyNode(6)
         n6=MyNode(8)
         n7=MyNode(3)
         #链表
         n1.next=n2
         n2.next=n3
         n3.next=n4
         n4.next=n5
         n5.next=n6
         n6.next=n7
         n7.next=n4
    
         #调方法
         print(hasCycle(n1))

> 扩展问题2: 如果链表有环，如何求出入环节点? 
> 
> 抽象示意图:
> 
> 从**链表头节点**到**入环点**的距离是**D**
> 
> 从**入环点**到两个指针**首次相遇点**的距离是**S1**
> 
> 从**首次相遇点**回到**入环点**的距离是**S2**

![2b7503f8ace34f559dd190090b84bce6.png][]

> 那么，当两个指针首次相遇时，各自所走的距离是多少呢?
> 
> 指针p1一次只走1步，所走的距离是D+S1。
> 
> 指针p2一次走2步，多走了n (n>=1）整圈，所走的距离是D+S1+n ( S1+S2)。
> 
> 由于p2的速度是p1的2倍，所以所走距离也是pi的2倍，因此: 2(D+S1)=D+S1+n(S1+S2)
> 
> 等式经过整理得出: **D=(n-1)(S1+S2)+S2**

[ace878220fe946cfabf21073627a7d9f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/7767b5bd0fac441d86d363a19022e954.png
[496a1994313840f693c0e3c025116397.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/3f6de40d059a4647bc60ab6e59be6d89.png
[cc8265526db1470188d173bf7de3306f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/13f0344957134116b524c46eacf29a76.png
[0625f565b9ad4e4ba60fd9d75fb77812.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/11da2b9255784cefbd4d77015eb40de3.png
[5f6e17276d024eccbab152e7872bb303.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/13673e44b4024faea1f0497daa60691c.png
[20954e6425d24465bf87b95682f8fc48.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/1ad15cde37464ecabcdad435a23237dc.png
[2b7503f8ace34f559dd190090b84bce6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/2efaf3df59d94ef2a2896d2250633022.png