下面的函数试图寻找nth到 最后 一个单向链表的元素。
nth
例如:
如果元素为,8->10->5->7->2->1->5->4->10->10则结果为 7th的最后一个节点为7。
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个节点)。