数据结构与算法之单链表面试题（新浪、百度、腾讯）

单链表面试题（新浪、百度、腾讯）

• 求单链表中的有效节点的个数

public int getCount(HeroNode head) {Hero1 cur = head.getNext();int count = 0;while(cur != null) {count++;cur = cur.getNext();}return count;}

• 查找单链表中的倒数第k个结点【新浪面试题】
  • 第一种思路：通过直接计算循环次数来实现查找
  • 第二种思路：定义两个结点n1，n2，先找到第k个结点n1，然后n1、n2结点同时移动。当n1到达链表尾部的后一个元素时，n2所指的就是倒数第k个结点。

/*** 返回倒数第k个结点* @param index* @return*/public Hero1 findLastIndexNode2(Hero1 head,int index) {if(head.getNext() == null) {return null;}// 找到第k个int count = getCount();if(index <= 0 || index > count) {return null;}Hero1 cur = head.getNext();for(int i = 0 ; i < count - index;i++) {cur = cur.getNext();}return cur;}/***第二种思路* @param index* @return*/public Hero1 findLastIndexNode(int index) {if(index < 0) return null;// 找到第k个Hero1 node1 = head.getNext();Hero1 node2 = head;// 代表有没有找到boolean flag = false;while(node1 != null) {index--;if(index == 0) {flag = true;break;}node1 = node1.getNext();}if(flag) {while(node1 != null) {node1 = node1.getNext();node2 = node2.getNext();}return node2;}else {return null;}}

• 单链表的反转【腾讯面试题】
  

public void reverseLinkedList(Hero1 head) {// 如果当前链表为空，或者只有一个节点，无需反转，直接返回if(head.getNext() == null || head.getNext().getNext() == null) {return;}// 创建一个新的头结点Hero1 newHead = new Hero1();Hero1 cur = head.getNext();Hero1 nextNode;while(cur != null) {nextNode = cur.getNext();cur.setNext(newHead.getNext());newHead.setNext(cur);cur = nextNode;}head.setNext(newHead.getNext());}

• 从尾到头打印单链表【百度，要求方式1：反向遍历。方式2：stack】
  

/*** 反向打印链表，利用栈的特性*/public void printReverse() {// 创建一个栈，将各个节点压入栈Stack<Hero1> stack = new Stack<>();Hero1 cur = head.getNext();// 将链表的所有节点压入栈while(cur != null) {stack.push(cur);cur = cur.getNext();}while(!stack.isEmpty()) {// 将所有的节点pop并打印Hero1 hero = stack.pop();System.out.println(hero);}}

• 合并两个有序的单链表，合并之后的链表依然有序

/*** 合并两个有序的链表，合并之后依然有序* @param list* @return*/public void mergeLinkList(SingleList list) {Hero1 cur1 = head;Hero1 cur2 = list.head.getNext();Hero1 next;while(cur1.getNext() != null && cur2 != null) {while(cur1.getNext() != null && cur1.getNext().getNo() <= cur2.getNo()) {cur1 = cur1.getNext();}next = cur2.getNext();cur2.setNext(cur1.getNext());cur1.setNext(cur2);cur1 = cur2;cur2 = next;}if(cur1.getNext() == null) {cur1.setNext(cur2);}}