所以我正在阅读《破解编码面试》一书。我正在解决这个问题:
“实现检查链表是否为回文的功能”
我注意到第一个解决方案(第217页)仅提供一个节点作为函数的参数,而不是整个列表。我只是想知道,在没有提供列表的情况下,函数如何知道列表中的下一个节点?
我提供了以下代码,以防万一。
boolean isPalindrome(LinkedListNode head){
LinkedListNode reversed = reverseAndClone(head);
return isEqual(head, reversed);
}
LinkedListNode reverseAndClone(LinkedListNode node){
LinkedListNode head = null;
while(node != null){
LinkedListNode n = new LinkedListNode(node.data);
n.next = head;
head = n;
node = node.next;
}
return head;
}
boolean isEqual(LinkedListNode one, LinkedListNode two) {
while(one != null && two != null){
if (one.data != two.data){
return false;
}
one = one.next;
two = two.next;
}
return one == null && two == null;
}
最佳答案
在链表中,每个节点都拥有自己的数据以及对链表中下一个节点的引用(也可能对双链表中的上一个项目进行引用,在这里似乎不是这种情况)。因此,您实际上并不需要列表包装器来获取其所有数据,只需引用第一个节点(头)即可,如您所包含的代码片段所示。