一种方法来解决三道链表相关的题目

今天小编就来和大家一块看三道链表相关的题目可以使用同一种方法来解决。虽然题目中用到了指针但我们知道Python是没有指针的所以在Python里面这里实际上指的是引用。不过由于“指针”这个词更加形象所以下文我们还是会用指针来表示对一个对象的应用。先来看我们将要解决的三道题目题目1只扫描一次链表O(1)空间复杂度返回链表倒数第 k 个节点。题目2只扫描一次链表O(1)空间复杂度返回链表中间的节点。题目3空间复杂度(1)查询链表是否有环。其中前两道题要求只能扫描链表一次。但是大家可能会有疑问例如对于第 2 题都不知道链表一共有多少个节点怎么可能知道中间的节点是哪个但如果提前把链表扫描一遍知道一共有多少个节点了又不能再次扫描链表那么就必须把每个节点和序号都存下来这样空间复杂度就不可能是O(1)了。我们先来看看第2题找到链表中间的节点。从下图的两个链表可以看到链表有 n 个节点如果 n 为奇数那么中间的节点在第(n 1) / 2个节点。如果 n 为偶数那么中间的节点在第n / 2个节点。这个信息怎么使用呢我们看下面一个表格既然如此如果我们在链表里面有两个指针引用其中一个每次移动2个节点另一个每次移动一个节点。这样当快的指针移动到了末尾慢的指针刚刚好指向中间的节点。用代码来表示def find_mid(node): if not node: return None if not node.next: return node fast slow node while fast.next and fast.next.next: slow slow.next fast fast.next.next return slow返回的 slow 就是最中间的节点。再来看第3道题。跟第二题一样也是一快一慢两个指针如果链表有环那么快的指针会绕到慢的指针的后面然后追上来。只要看快的指针是否跟慢的指针重合就知道是否有环了def find_cycle(node): if not node: return False slow fast node while fast: fast fast.next if not fast: # 快的指针到了链表末尾说明没有环 return False if fast is slow: # 快的指针追上了慢的指针说明有环 return True fast fast.next if fast is slow: return True slow slow.next return False