- 如何最快的获取单链表的中间节点的位置?
- 给定一个单链表,不知道节点总个数,怎样只遍历一次就知道中间节点?
最容易想到的一个方法是:首先先遍历一遍获得节点个数,然后取一半作计数器再次遍历。这个方法遍历了两次,是最慢的方法。附Python代码
class Node: def __init__(self, data, next): self.data = data self.next = next n1 = Node("n1", None) n2 = Node("n2", n1) n3 = Node("n3", n2) n4 = Node("n4", n3) n5 = Node("n5", n4) head = n5 # 链表的头节点 index = 0 # 总节点数 while head.next is not None: index += 1 head = head.next head = n5 for i in range(0, int(index / 2)): head = head.next print(head.data)
使用两个指针的方法,这个方法是面试题的正解。一个指针(P1)每次步进一个节点,另一个指针(P2)每次步进两个节点。当P2遍历到链表尾时,P1正好遍历到中间节点。附Python代码:
class Node: def __init__(self, data, next): self.data = data self.next = next n1 = Node("n1", None) n2 = Node("n2", n1) n3 = Node("n3", n2) n4 = Node("n4", n3) n5 = Node("n5", n4) head = n5 # 链表的头节点 P1 = head # 一次步进1个node P2 = head # 一次步进2个node while P2.next is not None and P2.next.next is not None: P2 = P2.next.next P1 = P1.next print(P1.data)