链表的面试题 ★精品★!!! 数据结构与算法（java）

这里写目录标题

求链表的有效长度
新浪面试题查找单链表中倒数第K个节点
腾讯面试题单链表的反转
百度面试题从头到尾打印单链表
合并连个有序的单链表，合并之后依然有序

【链表的面试题 ★精品★!!!】
求链表的有效长度

//方法获取到单链表的节点的个数（如果是带头结点的链表，需求不统计头节点）/** * * @param head 链表的头节点 * @return 返回的就是有效节点的个数 */ publicstaticintgetLength(HeroNode head){ int length=0; if (head.next==null){ return 0; } HeroNode cur =head; while (cur.next!=null){ length++; cur=cur.next; } return length; }

新浪面试题查找单链表中倒数第K个节点

//新浪面试题获取倒数第index个节点 //1 编写一个方法，接受head节点，同时接收一个index //2 index 表示是倒数第index个节点 //3 先把链表遍历一遍得到链表的有效程度getLength() //4 得到size后我们从链表的第一个开始遍历到（size-index）个，就可以的得到 //5 如果找到了，返回该节点，否则返回null publicstatic HeroNode findLastIndexMOde(HeroNode head,int index){ //判断是否为空 if(head.next==null){ return null; }intsize=getLength(head); if (index<=0||index>size){ return null; } //辅助变量 HeroNode cur =head.next; for (int i = 0; i < size - index; i++) { cur = cur.next; } return cur; }

腾讯面试题单链表的反转

//腾讯面试题（链表的反转）public static void reverseHead(HeroNode head) { //链表为空和只有一个节点时直接返回 if(head.next==null||head.next.next==null){ return; }//定义一个辅助变量 HeroNode cur=head.next; //指向当前节点的下一个节点 HeroNode next=null; //定义一个新的链表,没遍历一个节点，将其取出，并放在新建的链表reverseHead的最前端 HeroNode reverseHead=new HeroNode(0,"",""); while (cur!=null){ //先暂时保存当前节点的下一个节点，因为后面还需要使用 next=cur.next; //将cul的下一个节点指向新链表的最前端 cur.next=reverseHead.next; //将cul连接到新的链表上 reverseHead.next=cur; //cul后移 cur=next; } //实现head.next指向reverseHead.next，实现单链表的反转 head.next=reverseHead.next; }

百度面试题从头到尾打印单链表

思路：方式1反向遍历方式2 stack 栈

//逆序打印 //可以用栈这个数据结构，将各个节点压入栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果 publicstaticvoid reversePrint(HeroNode head){ //判断是否为空 if(head.next==null){ //链表为空不能打印 return; } HeroNode cur=head.next; //创建一个栈 Stack stack = new Stack<>(); //入栈 while (cur!=null){ stack.push(cur); cur=cur.next; } //出栈 while (stack.size()>0){ System.out.println(stack.pop()); }}

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

package com.atg.linkedlist; public class TextDemo01 { public static void main(String[] args) { Node node1 = new Node(2); Node node3 = new Node(3); node1.next = node3; Node node2 = new Node(1); Node node4 = new Node(4); Node node5 = new Node(5); node2.next = node4; node4.next = node5; System.out.println("单链表1"); print(node1); System.out.println("单链表2"); print(node2); System.out.println("合并后的单链表"); print(merge(node1,node2)); }/** * 合并有序单链表 * @param node1 * @param node2 * @return */ public static Node merge(Node node1,Node node2){ Node cur1 = node1; Node cur2 = node2; Node temp = new Node(0); Node cur = temp; while (true){ if(cur1 == null){ cur.next = cur2; break; } if(cur2 == null){ cur.next = cur1; break; }/*if (cur1.data