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)$

总结

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