复杂链表的复制、链表判环、无环单链表判相交

落日映苍穹つ 2022-06-09 04:51 172阅读 0赞

*   *   *  复杂链表的复制
         *  链表判环
         *  无环单链表判相交

--------------------

### 复杂链表的复制 ###

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）

**我的提交**

# -*- coding:utf-8 -*-
    # class RandomListNode:
    # def __init__(self, x):
    # self.label = x
    # self.next = None
    # self.random = None
    class Solution:
        # 返回 RandomListNode
        def Clone(self, pHead):
            # write code here
            if not pHead:
                return None
            p = pHead
            while p:
                node = RandomListNode(p.label)
                node.next = p.next
                p.next = node
                p = node.next
    
            p = pHead
            while p:
                node = p.next
                # 这里要注意：p.random 可能为空
                if p.random:
                    node.random = p.random.next
                p = node.next
    
            cHead = pHead.next
            cp = pHead.next
            p = pHead.next.next
            pHead.next = p
            while p:
                cp.next = p.next
                cp = p.next
                p.next = cp.next
                p = p.next
    
            return cHead

--------------------

### 链表判环 ###

如何判断一个单链表是否有环？有环的话返回进入环的第一个节点的值，无环的话返回-1。如果链表的长度为N，请做到时间复杂度O(N)，额外空间复杂度O(1)。

给定一个单链表的头结点head（注意另一个参数adjust为加密后的数据调整参数，方便数据设置，与本题求解无关)，请返回所求值。

> 参考：判断链表中是否有环 —– 有关单链表中环的问题  
> [http://blog.csdn.net/doufei\_ccst/article/details/10578315][http_blog.csdn.net_doufei_ccst_article_details_10578315]  
> 判断单链表是否存在环及求环入口点  
> [http://www.cnblogs.com/ccdev/archive/2012/09/06/2673618.html][http_www.cnblogs.com_ccdev_archive_2012_09_06_2673618.html]

**我的提交**

# -*- coding:utf-8 -*-
    # class ListNode:
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class ChkLoop:
        def chkLoop(self, head, adjust):
            # write code here
            slow = head
            fast = head
            while True:
                if not fast or not fast.next:
                    return -1
                slow = slow.next
                fast = fast.next.next
                if fast == slow:
                    break
    
            p = head
            while p != slow:
                p = p.next
                slow = slow.next
    
            return p.val

--------------------

### 无环单链表判相交 ###

现在有两个无环单链表，若两个链表的长度分别为m和n，请设计一个时间复杂度为O(n + m)，额外空间复杂度为O(1)的算法，判断这两个链表是否相交。

给定两个链表的头结点headA和headB，请返回一个bool值，代表这两个链表是否相交。保证两个链表长度小于等于500。

**我的提交**

# -*- coding:utf-8 -*-
    # class ListNode:
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class CheckIntersect:
        def chkIntersect(self, headA, headB):
            # write code here
            if not headA or not headB:
                return False
            pa = headA
            pb = headB
            n, m = 1, 1
            while pa.next:
                n += 1
                pa = pa.next
    
            while pb.next:
                m += 1
                pb = pb.next
    
            if pa != pb:
                return False
            # 如果只需要判断是否相交，则直接判断尾结点是否相同即可
            # else:
            # return True
            # 下面可找出第一个相交的结点
            pn = None
            pm = None
            if n > m:
                pn = headA
                pm = headB
            else:
                pn = headB
                pm = headA
    
            for _ in range(n - m):
                pn = pn.next
    
            while pn:
                if pn == pm:
                    # 此为第一个相交的结点
                    return True
                pn = pn.next
                pm = pm.next
            return False

[http_blog.csdn.net_doufei_ccst_article_details_10578315]: http://blog.csdn.net/doufei_ccst/article/details/10578315
[http_www.cnblogs.com_ccdev_archive_2012_09_06_2673618.html]: http://www.cnblogs.com/ccdev/archive/2012/09/06/2673618.html