十六、链表
访问 www.coding-time.cn 阅读原文动画效果，体验更佳。
1.链表遍历
我们的任务是顺序遍历给定的链表，比如下面的链表
遍历的顺序应该是
12 → 99 → 37
因为我们每个节点只访问一次，时间复杂度应该是O(n)
1）完整代码
/** * Traversal callback function. * @callback traversalCallback * @param {*} nodeValue */ /** * @param {LinkedList} linkedList * @param {traversalCallback} callback */export default function traversal(linkedList, callback) { let currentNode = linkedList.head; while (currentNode) { callback(currentNode.value); currentNode = currentNode.next; }}
2）参考
Wikipedia
2.链表倒序遍历
我们的任务是倒序遍历给定的链表，比如下面的链表
遍历的顺序应该是
37 → 99 → 12
因为我们每个节点只访问一次，时间复杂度应该是O(n)
1）完整代码
/** * Traversal callback function. * @callback traversalCallback * @param {*} nodeValue */ /** * @param {LinkedListNode} node * @param {traversalCallback} callback */function reverseTraversalRecursive(node, callback) { if (node) { reverseTraversalRecursive(node.next, callback); callback(node.value); }} /** * @param {LinkedList} linkedList * @param {traversalCallback} callback */export default function reverseTraversal(linkedList, callback) { reverseTraversalRecursive(linkedList.head, callback); }
2）参考
Wikipedia
