leetcode链表问题

2021/02/24 leetcode
如果文章图片无法显示,可尝试配置host:修复Github图片资源无法显示问题

1、两个链表的公共节点

原题地址:剑指 Offer 52. 两个链表的第一个公共节点

解题思路:

  • 哈希表法 时间O(n+m) 空间O(n+m)
  • 双指针遍历法 时间O(n+m) 空间O(1)

(1)哈希法:

两次遍历:

  • 第一次遍历list1,存储list1 的全部节点到set
  • 第二次遍历list2,对比set集合中的就
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        myset = set()
        cura, curb = headA, headB
        while cura:
            myset.add(cura)
            cura = cura.next

        while curb:
            if curb in myset:
                return curb
            curb = curb.next
        return

(2)双指针遍历法

利用双指针进行两个节点的遍历,如果两个指针相遇则证明当前两个链表有公共节点

"""
输入两个链表,找出它们的第一个公共节点
"""

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


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        cur_a, cur_b = headA, headB
        while cur_a != cur_b:
            cur_a = cur_a.next if cur_a else headB
            cur_b = cur_b.next if cur_b else headA
        return cur_a

2、环形链表

2-1 判断一个链表是否是环形链表

原题地址:https://leetcode-cn.com/problems/linked-list-cycle/

解题思路:

  • 使用set :通用思路,没什么亮点主要是空间复杂度比较高

  • 快慢指针:在空间上进行了优化

"""
使用set
时间复杂度:O(n)
空间复杂度:O(n)
"""
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        myset = set()
        cur = head
        while cur:
            if cur in myset:
                return True
            myset.add(cur)
            cur = cur.next
        return False
"""
快慢指针法
时间复杂度:O(n)
空间复杂度:O(1)
"""

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

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next: return False  # 保证至少有两个值
        slow = head
        fast = head.next

        while True:
            if slow == fast: return True
            # 出现 null 则证明不是环形链表
            if not slow or not slow.next or not fast.next or not fast.next.next: return False  
            slow = slow.next
            fast = fast.next.next

2-2 如果一个链表是环形链表,求入环节点

原题地址:https://leetcode-cn.com/problems/linked-list-cycle-ii/

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

class Solution(object):
    def detectCycle(self, head):
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast

fig1

假设快慢指针在紫点处相遇

假设fast走了n圈,则

fast走的路程:len_fast = a+n(b+c)+b ,而且fast走的路程是slow的二倍,且len_slow = a+b

则有:a+n(b+c) +b= 2(a+b),化简得 a=c+(n-1)(b+c)

含义为:当fast保证和slow相同速度(每次走1步)重新从a开头走到相交点的话,slow需要走相遇点走到c,并且需要多走n-1圈,但是最后其能保证fast和slow能在交点相遇


公众号:豆仔gogo

golang、算法、后端知识、面试手册

豆仔gogo

Search

    公众号:豆仔gogo

    豆仔gogo

    Post Directory