如何从单链列表的末尾找到第n个元素?
问题内容:
下面的函数试图寻找nth
到 最后 一个单向链表的元素。
例如:
如果元素为,8->10->5->7->2->1->5->4->10->10
则结果为 7th
的最后一个节点为7
。
有人可以帮助我解决这段代码的工作方式吗,或者有更好,更简单的方法吗?
LinkedListNode nthToLast(LinkedListNode head, int n) {
if (head == null || n < 1) {
return null;
}
LinkedListNode p1 = head;
LinkedListNode p2 = head;
for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead
if (p2 == null) {
return null; // not found since list size < n
}
p2 = p2.next;
}
while (p2.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
问题答案:
您的算法通过首先创建对链表中两个节点(相距N个节点)的引用来工作。因此,在您的示例中,如果N为7,则它将p1设置为8,p2设置为4。
然后它将每个节点引用前进到列表中的下一个节点,直到p2到达列表中的最后一个元素。同样,在您的示例中,这将是p1为5且p2为10时。在这一点上,p1指的是列表中最后一个元素的第N个元素(通过属性,它们相距N个节点)。