当前位置: 首页 > >

前端面试中常见的数据结构题

发布时间:

一、链表


1、如何判断一个链表里有没有环


思路:快慢指针,一个走的快,一个走的慢,那么若干步以后,快慢指针会相遇。


/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/

var hasCycle = function(head) {
if( head == null || head.next == null ){
return false;
}
var slow = head; //slow pointer moves one step forward
var fast = head; //fast pointer moves two steps forward
while( true ){
if( fast.next == null || fast.next.next == null ){
return false;
}
slow = slow.next;
fast = fast.next.next;
if( fast === slow ){
return true;
}
}
};

2、链表的反转(递归法)


/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if(head == null || head.next == null )
return head;
var nextNode = head.next;
var newHead = reverseList(nextNode);
nextNode.next = head;
head.next = null;
return newHead;
};

3、删除链表的某个节点


/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function(head, val) {
if (head == null) return null;
var node = head;
while(node != null && node.next != null){
if(node.next.val == val){
node.next = node.next.next;
}
else{
node = node.next;
}
}

return head.val == val ? head.next : head;
};

二、栈和队列


1、用两个栈实现一个队列


我们现在有两个栈,一个直观的想法是将数据在两个栈之间移动,以便能够达到先进先出的目的。假设这两个栈为栈A和栈B,栈A用来接收 enqueue 的数据,栈B用来 dequeue 数据,具体的算法为:


enqueue:
(1) 直接将数据压入栈A


dequeue:
(1) 如果栈B不为空,将栈B顶端的数据弹出
(2) 如果栈B为空,先将栈A中所有数据弹出,压入栈B,再将栈B顶端的数据弹出


2、用两个队列实现栈


假设我们现在有队列A和队列B,因为比较直观,直接上算法:


push:
(1) 将元素加入队列A


pop:
(1) 将队列A的size大于1时,循环将队列A中的元素移动到队列B
(2) 将队列A中最后剩下的元素出队列并作为结果返回
(3) 交换队列A和队列B的名字



友情链接: 时尚网 总结汇报 幼儿教育 小学教育 初中学习资料网