找到单链表中间节点-面试题

面试常见问题:

  • 如何最快的获取单链表中间节点的位置?
  • 给定一个单链表,不知道节点总个数,怎样只遍历一次就知道中间节点?

最容易想到的一个方法是:首先先遍历一遍获得节点个数,然后取一半作计数器再次遍历。这个方法遍历了两次,是最慢的方法。Python代码:

找到单链表中间节点-常见面试题

使用两个指针的方法,这个方法是面试题的正解。一个指针(P1)每次步进一个节点,另一个指针(P2)每次步进两个节点。当P2遍历到链表尾时,P1正好遍历到中间节点。Python代码:

找到单链表中间节点-面试题

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注