单向链表中,获取正数第 N 个节点的方法,只需要从 head 向后前进 N 步即可。
代码:
In [1]: class Node: ...: def __init__(self, value, next=None): ...: self.value = value ...: self.next = next In [2]: def get(n, head): ...: node = head ...: for i in range(n): ...: node = node.next ...: return node.value # 定义一个链表 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None In [3]: node6 = Node(6) ...: node5 = Node(5, node6) ...: node4 = Node(4, node5) ...: node3 = Node(3, node4) ...: node2 = Node(2, node3) ...: node1 = Node(1, node2) In [4]: get(0, node1) Out[4]: 1 In [5]: get(1, node1) Out[5]: 2 In [6]: get(4, node1) Out[6]: 5
因为单向链表无法获取当前节点之前的数据信息。所以1个指针无法完成这个工作,需要第二个指针,在第一个节点出发 N 步之后再出发,这样在第一个指针到达链表终点的时候, 第二个指针停留的位置即是倒数第 N 个节点。
下图展示了求倒数第三个节点的过程:
代码:
In [1]: class Node: ...: def __init__(self, value, next=None): ...: self.value = value ...: self.next = next # 定义一个链表 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None In [2]: node6 = Node(6) ...: node5 = Node(5, node6) ...: node4 = Node(4, node5) ...: node3 = Node(3, node4) ...: node2 = Node(2, node3) ...: node1 = Node(1, node2) In [3]: def get_reverse(n, head): ...: pnt_a = pnt_b = head ...: # 指针 a 先走 N 步 ...: try: ...: for i in range(n): ...: pnt_a = pnt_a.next ...: # 当链表长度小于 N 时, 返回 None ...: except AttributeError: ...: return None ...: # 两个指针开始同步前进,直到指针 a 到达终点 ...: while pnt_a: ...: pnt_a = pnt_a.next ...: pnt_b = pnt_b.next ...: return pnt_b.value In [4]: get_reverse(1, node1) Out[4]: 6 In [5]: get_reverse(3, node1) Out[5]: 4 In [6]: get_reverse(10, node1)