思路:
单向链表中,获取正数第 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
获取反向第 N 个节点。
因为单向链表无法获取当前节点之前的数据信息。所以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)