大厂前端面试题集锦!

开课吧开课吧锤锤2021-06-28 15:50

    前端入门容易,工资高,现在也是国内稀缺的岗位。既然前端这么受欢迎,对于零基础想转行的同学来说,下面这个面试题是你现在最需要的。

web

    手写单链表查找倒数第k个节点

    1、为了找出倒数第k个元素,最容易想到的办法是首先遍历一遍单链表,求出整个单链表的长度n,然后将倒数第k个,转换为正数第n-k个,接下来遍历一次就可以得到结果。但是该方法存在一个问题,即需要对链表进行两次遍历,第一次遍历用于求解单链表的长度,第二次遍历用于查找正数第n-k个元素。

    这种思路的时间复杂度是O(n),但需要遍历链表两次。

    2、如果我们在遍历时维持两个指针,第一个指针从链表的头指针开始遍历,在第k-1步之前,第二个指针保持不动;在第k-1步开始,第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1,当第一个(走在前面的)指针到达链表的尾结点时,第二个指针(走在后面的)指针正好是倒数第k个结点。这种思路只需要遍历链表一次。对于很长的链表,只需要把每个结点从硬盘导入到内存一次。因此这一方法的时间效率前面的方法要高。

class Node{
	Node next=null;
	int data;
	public Node(int data){
		this.data=data;
	}
}
public class MyLinkedList {

	Node head=null;//链表头的引用
	public Node findElem(Node head,int k){
		if(k<1||k>this.length()){
			return null;
		}
		Node p1=head;
		Node p2=head;
		for(int i=0;i<k;i++)
			p1=p1.next;
		while(p1!=null){
			p1=p1.next;
			p2=p2.next;
		}
		return p2;
	}
	public static void main(String[] args) {
		
		MyLinkedList list=new MyLinkedList();
		list.addNode(1);
		list.addNode(2);
		list.addNode(3);
		list.addNode(4);
		list.addNode(5);
		MyLinkedList p=new MyLinkedList();
		p.head=list.findElem(list.head, 3);
		p.printList();
		
	}

}

    假如您对大厂的面试题有兴趣,不妨点击下面的图片,免费领取。

web

    在线搜索Web面试题,你会发现很多都是重复性的,那么精粹的面试题,就是你最需要的。以上就是开课吧广场小编为大家整理发布的“大厂前端面试题集锦!”一文,更多Web面试相关内容尽在开课吧广场Web面试频道!

免责声明:本站所提供的内容均来源于网友提供或网络搜集,由本站编辑整理,仅供个人研究、交流学习使用。如涉及版权问题,请联系本站管理员予以更改或删除。
有用
分享