乐趣区

关于leetcode:Leetcode双指针系列2

19. 删除链表的倒数第 N 个节点
141. 环形链表
142. 环形链表 II
160. 相交链表

19. 删除链表的倒数第 N 个节点

题目形容

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5.

阐明:
给定的 n 保障是无效的。

进阶:
你能尝试应用一趟扫描实现吗?

思路

设置两个指针, 第一个向走 n 步, 而后两个指针一起往前走, 当第一个指针达到链表开端时, 第二个指针刚好指向倒数第 n 个元素

def removeNthFromEnd(head, n):  
    if n < 1 or head == None:  
        return head  

    p_fast = p_slow = head    
    
    # 快指针先往前挪动 n 步
    for i in range(n):  
        p_fast = p_fast.next  
    
    # 如果此时 fast 指针为 None, 则要删除的节点为头节点
    if p_fast == None:  
        return head.next  
    
    # 快慢指针同时后退
    while p_fast.next != None:  
        p_fast = p_fast.next  
        p_slow = p_slow.next  
        
    p_slow.next = p_slow.next.next  
    return head

工夫复杂度为 $O(n)$, 空间复杂度为 $O(1)$

141. 环形链表

给定一个链表,判断链表中是否有环。

为了示意给定链表中的环,咱们应用整数 pos 来示意链表尾连贯到链表中的地位(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。

示例 1:

输出:head = [3,2,0,-4], pos = 1 输入:true 解释:链表中有一个环,其尾部连贯到第二个节点。

示例 2:

输出:head = [1,2], pos = 0 输入:true 解释:链表中有一个环,其尾部连贯到第一个节点。

示例 3:

输出:head = [1], pos = -1 输入:false 解释:链表中没有环。

进阶:

你能用 O(1)(即,常量)内存解决此问题吗?

一个直观的想法是应用字典记录每个节点的拜访状态, 如果曾经被拜访, 则返回 False

def hasCycle(head):  
    if not head:  
        return False  
   
     dicts = {}  
     while head:  
         if head in dicts:  
            return True  
        dicts[head] = 1  
        head = head.next  

     return False

工夫复杂度为 $O(n)$, 空间复杂度为 $O(n)$

思路 2, 双指针

设置 2 个速度不一样的指针, 别离为 p1 和 p2, p1 每次前进一步, p2 每次后退 2 步.

如果链表中不蕴含环, 则 p2 会先达到起点, 此时完结, 返回 False

如果链表蕴含环, 则 p2 最初会赶上 p1, 此时完结, 返回 True

def hasCycle(head):  
    if (not head) or (not head.next):  
       return False  

    p1 = head  
    p2 = head.next  
    
    while p1 != p2:
       
       p1 = p1.next  
       if not p2 or not p2.next:  
          return False  
       p2 = p2.next.next  
       
    return True

工夫复杂度为 $O(n)$, 空间复杂度为 $O(1)$

142. 环形链表 II

给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 null。

为了示意给定链表中的环,咱们应用整数 pos 来示意链表尾连贯到链表中的地位(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。

阐明:不容许批改给定的链表。

示例 1:

输出:head = [3,2,0,-4], pos = 1 输入:tail connects to node index 1 解释:链表中有一个环,其尾部连贯到第二个节点。

示例 2:

输出:head = [1,2], pos = 0 输入:tail connects to node index 0 解释:链表中有一个环,其尾部连贯到第一个节点。

示例 3:

输出:head = [1], pos = -1 输入:no cycle 解释:链表中没有环。

进阶:你是否能够不必额定空间解决此题?

和上题一样, 同样能够应用字典来解决

def detectCycle(head):  
    if not head or not head.next:  
        return None  
    dicts = {}  

    p = head  
    while p:  
        if p in dicts:  
            return p  
        else:  
            dicts[p] = 0  
        p = p.next  

    return None

工夫复杂度为 $O(n)$, 空间复杂度为 $O(n)$

思路 2
如下图所示, 最右边红色节点示意链表的起始节点 p_start, 两头红色节点示意环形链表的入口节点 p_entrance, 左边红色节点示意快慢节点第一次相遇的节点 p_inter.

p_start 到 p_entrance 之间的间隔为 F, p_entrance 到 p_inter 之间的间隔为 a, p_inter 到 p_entrance 之间的间隔为 b.

快慢指针同时后退, 在 p_iter 相遇, 则有如下公式成立
$2(F+a) = (F+a+b + a) + 1$
即失去
$F=b+1$

def detectCycle(head):  
    if not head or not head.next:  
        return None  
    #设置快慢指针, 快指针是从第二个节点登程  
    fast = head.next  
    slow = head  

    # has_cycle =   
    inter_node = None  

    # 快指针和慢指针同时登程  
    while fast and fast.next:  
        # 当快指针和慢指针指向同一地位时, 退出循环  
        if fast == slow:  
            inter_node = fast  
            break  
        fast = fast.next.next  
        slow = slow.next  

    # 如果 inter_node 为 None, 阐明无环
    if not inter_node:  
        return None  

    fast = head  
    slow = inter_node.next  


    while fast != slow:  
        fast = fast.next  
        slow = slow.next  

    return slow

总体的思路

  • 设置快指针 (每次走 2 步) 和慢指针(每次走 1 步), 同时登程, 如果最初快指针和慢指针指向同一地位, 阐明有环.
  • 将快指针后移一个节点, 慢指针指向 head 节点, 而后同时以雷同的速度登程.
  • 直至相遇, 返回相遇节点.

160. 相交链表

编写一个程序,找到两个单链表相交的起始节点。

如上面的两个链表:

在节点 c1 开始相交。

示例 1:

输出:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输入:Reference of the node with value = 8 输出解释:相交节点的值为 8(留神,如果两个链表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:

输出:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输入:Reference of the node with value = 2 输出解释:相交节点的值为 2(留神,如果两个链表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:

输出:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输入:null 输出解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。因为这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 能够是任意值。解释:这两个链表不相交,因而返回 null。

留神:

如果两个链表没有交点,返回 null. 在返回后果后,两个链表仍须放弃原有的构造。可假定整个链表构造中没有循环。程序尽量满足 O(n) 工夫复杂度,且仅用 O(1) 内存。

思路 1: 应用堆栈

def getIntersectionNode(headA: ListNode, headB: ListNode):
    if not headA or not headB:  
        return None  

    stacka = []  
    stackb = []  

    pa = headA  
    pb = headB  

    # 将链表 a 所有节点入栈  
    while pa:  
        stacka.append(pa)  
        pa = pa.next  

    # 将链表 b 所有节点入栈  
    while pb:  
        stackb.append(pb)  
        pb = pb.next  

    res = None  
    pa = stacka.pop()  
    pb = stackb.pop()  

    # 顺次出栈  
    while pa == pb:  
        res = pa  
        if not stacka or not stackb:  
            break  
        pa = stacka.pop()  
        pb = stackb.pop()  

    return res

工夫复杂度 $O(m+n)$, 空间复杂度 $O(m+n)$

思路 2:

应用字典

def getIntersectionNode(headA: ListNode, headB: ListNode):  
    if not headA or not headB:  
        return None  

    dicts = {}  
    pa = headA  
    while pa:  
        dicts[pa] = 1  
        pa = pa.next  

    pb = headB  
    while pb:  
        # 如果该节点曾经在字典中, 则能够间接返回  
        if pb in dicts:  
            return pb  
        pb = pb.next  

    return None

工夫复杂度为 $O(m+n)$, 空间复杂度为 $O(m)$ 或 $O(n)$

思路 3

双指针

  • 设置指针 p1, p2 别离在 headA 和 headB 上挪动
  • 如果 p1 指向 None, 则将 p1 指向 headB 持续遍历
  • 如果 p2 指向 None, 则将 p2 指向 headA 持续遍历
  • 如果 p1 和 p2 指向的节点雷同, 且不为 None, 则找到了相交节点

在遍历的过程中, 两个指针为了放弃同一进度, 打消长度差. 当较长的链表指针指向较短链表 head 时, 长度差就能够打消

def getIntersectionNode(headA: ListNode, headB: ListNode):  
    if not headA or not headB:  
        return None  

    p1 = headA  
    p2 = headB  

    while p1 != p2:  
        p1 = headB if not p1 else p1.next  
        p2 = headA if not p2 else p2.next  

    return p1

最初遍历的次数为, 工夫复杂度为 $O(m+n)$, 空间复杂度为​$O(1)$

总结

这里介绍了几道对于快慢指针的题目, 快慢指针在链表中非常常见, 尤其是遇到环形链表, 穿插链表等这类问题时, 都能够应用快慢指针来解决问题. 它们的思路通常都是利用门路差来失去要害节点地位, 从而求解问题.

退出移动版