单链表面试题：
求单链表中有效节点的个数查找单链表中的倒数第 k 个结点 【新浪面试题】单链表的反转【腾讯面试题】从尾到头打印单链表 【百度，要求方式 1：反向遍历 。 方式 2：Stack 栈】合并两个有序的单链表，合并之后的链表依然有序
1.求单链表中有效节点的个数
思路：有效节点指的是含有数据的节点，不算头节点。只需要从头开始遍历就好
/*** @Description: getLinkListLength 查询单链表的长度*/public static int getLinkListLength(HeroNode heroNode){int length = 0;if (heroNode.getNext() == null){//单链表为空return length;}HeroNode cur = heroNode.getNext();while (cur != null){length ++;cur = cur.getNext();}return length;}
2.查找单链表中的倒数第 k 个结点 【新浪面试题】
思路：先获取长度，那么倒数第k个节点等于正数第（length-k）个节点（从0开始算）
/*** @Description: getLinkListLastIndexOf 获取第k个节点*/public static HeroNode getLinkListLastIndexOf(HeroNode heroNode, int k){int linkListLength = getLinkListLength(heroNode);HeroNode cur = heroNode.getNext();for (int i=0; i < linkListLength - k; i++){cur = cur.getNext();}return cur;}
3.单链表的反转【腾讯面试题】
思路：
先构建一个新的头节点遍历原来单链表节点，每一次将遍历到的节点插入到新的头节点的第一个节点位置原来链表.next = 新链表.next
/*** @Description: reverseHeroNode 单链表反转*/public static void reverseHeroNode(HeroNode heroNode){if (heroNode.getNext() == null){return;//单链表为空}// 1. 构建一个新的节点HeroNode newHerNode = new HeroNode(0,"","");// 获取第一个节点HeroNode cur = heroNode.getNext();HeroNode next = null;while (cur != null){// 获取当前节点的下一个节点next = cur.getNext();// 2.1 将当前节点的next指向新链表的第一个节点cur.setNext(newHerNode.getNext());// 2.2 将新链表的头节点指向当前的节点newHerNode.setNext(cur);cur = next;}// 将原来链表的next域指向新链表的第一个节点heroNode.setNext(newHerNode.getNext());}
4.从尾到头打印单链表 【百度面试题】
思路：
方式一：使用方向遍历，但是这种会改变原来的链表的结构，不建议使用方式二：利用栈stack的先进后出的特性，遍历每一个节点，然后加入栈。最后再出栈方式三：遍历每一个节点，加入一个新的list，倒序打印。
这里使用方式二实现：
/*** @Description: reversePrintLn 倒序打印*/public static void reversePrintLn(HeroNode heroNode){HeroNode cur = heroNode.getNext();Stack<HeroNode> heroNodes = new Stack<>();while (cur != null){heroNodes.push(cur);cur = cur.getNext();}while (heroNodes.size() > 0){System.out.println(heroNodes.pop());}}
5.合并两个有序的单链表，合并之后的链表依然有序
思路：
法一：
获取两个有序链表的长度利用for循环链表总长度，判断两个链表的索引的大小，根据按顺序加入到新的链表。
/*** @Description: mergeNode 合并有序链表* @param heroNode1* @param heroNode2*/public static SingleLinkedList mergeNode(HeroNode heroNode1, HeroNode heroNode2){int linkListLength = getLinkListLength(heroNode1);int linkListLength2 = getLinkListLength(heroNode2);int length = linkListLength+linkListLength2;HeroNode cur1 = heroNode1.getNext();HeroNode cur2 = heroNode2.getNext();SingleLinkedList singleLinkedList = new SingleLinkedList();HeroNode cur = null;for (int i = 0; i < length; i++) {if (cur1 != null && cur2 != null){if (cur1.getNo() < cur2.getNo()){cur = new HeroNode();cur.setNo(cur1.getNo());cur.setName(cur1.getName());cur.setNckName(cur1.getNckName());singleLinkedList.add(cur);cur1 = cur1.getNext();}else {cur = new HeroNode();cur.setNo(cur2.getNo());cur.setName(cur2.getName());cur.setNckName(cur2.getNckName());singleLinkedList.add(cur);cur2 = cur2.getNext();}}else if (cur1 == null){cur = new HeroNode();cur.setNo(cur2.getNo());cur.setName(cur2.getName());cur.setNckName(cur2.getNckName());singleLinkedList.add(cur);cur2 = cur2.getNext();}else {cur = new HeroNode();cur.setNo(cur1.getNo());cur.setName(cur1.getName());cur.setNckName(cur1.getNckName());singleLinkedList.add(cur);cur1 = cur1.getNext();}}return singleLinkedList;}/*** @Description: 添加节点* 思路：* 1.先找到当前链表的最后节点* 2.将最后这个节点的next域指向新的节点*/public void add(HeroNode heroNode){// 辅助遍历变量HeroNode temp = head;// 遍历链表，找到最后while (true){//找到链表最后,并添加if (temp.getNext() == null){temp.setNext(heroNode);break;}// 如果没有找到最后，将temp后移temp = temp.getNext();}}
法二：
依次循环两个链表，然后将链表的内容加入到新的链表，加入时判断顺序关系进行添加
/*** @Description: mergeNode 合并有序链表* @param heroNode1* @param heroNode2*/public static SingleLinkedList mergeNode(HeroNode heroNode1, HeroNode heroNode2){HeroNode cur1 = heroNode1.getNext();HeroNode cur2 = heroNode2.getNext();SingleLinkedList singleLinkedList = new SingleLinkedList();HeroNode cur = null;while (cur1 != null){cur = new HeroNode();cur.setNo(cur1.getNo());cur.setName(cur1.getName());cur.setNckName(cur1.getNckName());singleLinkedList.addOrder(cur);cur1 = cur1.getNext();}while (cur2 != null){cur = new HeroNode();cur.setNo(cur2.getNo());cur.setName(cur2.getName());cur.setNckName(cur2.getNckName());singleLinkedList.addOrder(cur);cur2 = cur2.getNext();}return singleLinkedList;}/*** @Description: addOrder 按照编号顺序添加*/public void addOrder(HeroNode heroNode){HeroNode temp = head;// 标识英雄是否找到boolean flag = false;while (true){// 到了链表最后if (temp.getNext() == null){break;}//找到位置if (temp.getNext().getNo() > heroNode.getNo()){break;}else if (temp.getNext().getNo() == heroNode.getNo()){// 说明需要添加的heroNode的标号已经存在flag = true;break;}// 如果没有找到最后，将temp后移temp = temp.getNext();}if (flag){// 不能添加，编号已存在System.out.printf("准备插入的英雄编号%d已经存在，不能加入",temp.getNext().getNo());}else {// 添加heroNode.setNext(temp.getNext());temp.setNext(heroNode);}}
附完整完整代码：
节点：
public class HeroNode {private int no;private String name;private String nckName;private HeroNode next;//下一个节点public int getNo() {return no;}public void setNo(int no) {this.no = no;}public String getName() {return name;}public void setName(String name) {this.name = name;}public String getNckName() {return nckName;}public void setNckName(String nckName) {this.nckName = nckName;}public HeroNode getNext() {return next;}public void setNext(HeroNode next) {this.next = next;}public HeroNode(int no, String name, String nckName) {this.no = no;this.name = name;this.nckName = nckName;}public HeroNode() {}@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +", nckName='" + nckName + '\'' +'}';}}
节点操作
public class SingleLinkedList {private HeroNode head = new HeroNode(0,"","");public HeroNode getHead() {return head;}/*** @Description: 添加节点* 思路：* 1.先找到当前链表的最后节点* 2.将最后这个节点的next域指向新的节点*/public void add(HeroNode heroNode){// 辅助遍历变量HeroNode temp = head;// 遍历链表，找到最后while (true){//找到链表最后,并添加if (temp.getNext() == null){temp.setNext(heroNode);break;}// 如果没有找到最后，将temp后移temp = temp.getNext();}}/*** @Description: addOrder 按照编号顺序添加*/public void addOrder(HeroNode heroNode){HeroNode temp = head;// 标识英雄是否找到boolean flag = false;while (true){// 到了链表最后if (temp.getNext() == null){break;}//找到位置if (temp.getNext().getNo() > heroNode.getNo()){break;}else if (temp.getNext().getNo() == heroNode.getNo()){// 说明需要添加的heroNode的标号已经存在flag = true;break;}// 如果没有找到最后，将temp后移temp = temp.getNext();}if (flag){// 不能添加，编号已存在System.out.printf("准备插入的英雄编号%d已经存在，不能加入",temp.getNext().getNo());}else {// 添加heroNode.setNext(temp.getNext());temp.setNext(heroNode);}}/*** @Description: update 根据no更新信息*/public void update(HeroNode heroNode){HeroNode temp = head;if (temp.getNext() == null){System.out.println("链表为空~~~~~~~");return;}// 标识是否找到该节点boolean flag = false;while (true){if (temp.getNext() == null){break;}if (temp.getNext().getNo() == heroNode.getNo()){// 找到要修改的节点的前一个位置flag = true;break;}// 如果没有找到最后，将temp后移temp = temp.getNext();}if (flag){// 更新信息HeroNode next = temp.getNext();next.setName(heroNode.getName());next.setNckName(heroNode.getNckName());}else {System.out.printf("没有找到编号%d的节点，不能修改\n",heroNode.getNo());}}/*** @Description: deleteNode 删除节点，从要删除节点的上一个位置直接指向要删除节点的下一个位置，该节点会被垃圾回收机制回收*/public void deleteNode(HeroNode heroNode){HeroNode temp = head;// 表示是否找到节点信息boolean flag = false;while (true){if (temp.getNext() == null){break;}if (temp.getNext().getNo() == heroNode.getNo()){flag = true;break;}// 如果没有找到最后，将temp后移temp = temp.getNext();}if (flag){// 从要删除节点的上一个位置直接指向要删除节点的下一个位置，该节点会被垃圾回收机制回收temp.setNext(temp.getNext().getNext());}else {System.out.println("未找到该节点信息");}}/*** @Description: 显示链表*/public void show(){if(head.getNext() == null){System.out.println("链表为空");return;}HeroNode temp = head.getNext();while (true){if (temp == null){break;}// 输出节点信息System.out.println(temp);// 将temp后后移temp = temp.getNext();}}/*** @Description: getLinkListLength 查询单链表的长度*/public static int getLinkListLength(HeroNode heroNode){int length = 0;if (heroNode.getNext() == null){//单链表为空return length;}HeroNode cur = heroNode.getNext();while (cur != null){length ++;cur = cur.getNext();}return length;}/*** @Description: getLinkListLastIndexOf 获取第k个节点*/public static HeroNode getLinkListLastIndexOf(HeroNode heroNode, int k){int linkListLength = getLinkListLength(heroNode);HeroNode cur = heroNode.getNext();for (int i=0; i < linkListLength - k; i++){cur = cur.getNext();}return cur;}/*** @Description: reverseHeroNode 单链表反转*/public static void reverseHeroNode(HeroNode heroNode){if (heroNode.getNext() == null){return;//单链表为空}// 1. 构建一个新的节点HeroNode newHerNode = new HeroNode(0,"","");// 获取第一个节点HeroNode cur = heroNode.getNext();HeroNode next = null;while (cur != null){// 获取当前节点的下一个节点next = cur.getNext();// 2.1 将当前节点的next指向新链表的第一个节点cur.setNext(newHerNode.getNext());// 2.2 将新链表的头节点指向当前的节点newHerNode.setNext(cur);cur = next;}// 将原来链表的next域指向新链表的第一个节点heroNode.setNext(newHerNode.getNext());}/*** @Description: reversePrintLn 倒序打印*/public static void reversePrintLn(HeroNode heroNode){HeroNode cur = heroNode.getNext();Stack<HeroNode> heroNodes = new Stack<>();while (cur != null){heroNodes.push(cur);cur = cur.getNext();}while (heroNodes.size() > 0){System.out.println(heroNodes.pop());}}/*** @Description: mergeNode 合并有序链表* @param heroNode1* @param heroNode2*/public static SingleLinkedList mergeNode(HeroNode heroNode1, HeroNode heroNode2){HeroNode cur1 = heroNode1.getNext();HeroNode cur2 = heroNode2.getNext();SingleLinkedList singleLinkedList = new SingleLinkedList();HeroNode cur = null;while (cur1 != null){cur = new HeroNode();cur.setNo(cur1.getNo());cur.setName(cur1.getName());cur.setNckName(cur1.getNckName());singleLinkedList.addOrder(cur);cur1 = cur1.getNext();}while (cur2 != null){cur = new HeroNode();cur.setNo(cur2.getNo());cur.setName(cur2.getName());cur.setNckName(cur2.getNckName());singleLinkedList.addOrder(cur);cur2 = cur2.getNext();}return singleLinkedList;}}
测试链表;
public class TestSingleLinkedList {public static void main(String[] args) {SingleLinkedList singleLinkedList = new SingleLinkedList();HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");HeroNode heroNode3 = new HeroNode(3, "无用", "智多星");HeroNode heroNode4 = new HeroNode(6, "林冲", "豹子头");// System.out.println("按照顺序添加的顺序");// singleLinkedList.add(heroNode1);// singleLinkedList.add(heroNode2);// singleLinkedList.add(heroNode3);// singleLinkedList.add(heroNode4);// singleLinkedList.show();System.out.println("不按照顺序添加的顺序");singleLinkedList.addOrder(heroNode1);singleLinkedList.addOrder(heroNode4);singleLinkedList.addOrder(heroNode3);singleLinkedList.addOrder(heroNode2);singleLinkedList.show();// System.out.println("修改节点信息");// heroNode3.setName("吴用");// singleLinkedList.update(heroNode3);// singleLinkedList.show();//// System.out.println("删除节点");// singleLinkedList.deleteNode(heroNode3);// singleLinkedList.show();// int linkListLength = SingleLinkedList.getLinkListLength(singleLinkedList.getHead());// System.out.println("linkListLength = " + linkListLength);//// HeroNode linkListLastIndexOf = SingleLinkedList.getLinkListLastIndexOf(singleLinkedList.getHead(), 1);// System.out.println("linkListLastIndexOf = " + linkListLastIndexOf);// 反转链表// System.out.println("反转链表");// SingleLinkedList.reverseHeroNode(singleLinkedList.getHead());// singleLinkedList.show();// System.out.println("倒序打印");// SingleLinkedList.reversePrintLn(singleLinkedList.getHead());System.out.println("第二个单链表");SingleLinkedList singleLinkedList2 = new SingleLinkedList();HeroNode heroNode5 = new HeroNode(4, "武松", "行者");HeroNode heroNode6 = new HeroNode(7, "李逵", "黑旋风");HeroNode heroNode7 = new HeroNode(8, "花容", "小李广");HeroNode heroNode8 = new HeroNode(9, "鲁智深", "花和尚");singleLinkedList2.addOrder(heroNode5);singleLinkedList2.addOrder(heroNode6);singleLinkedList2.addOrder(heroNode7);singleLinkedList2.addOrder(heroNode8);singleLinkedList2.show();System.out.println("合并后的链表");SingleLinkedList slist = SingleLinkedList.mergeNode(singleLinkedList.getHead(),singleLinkedList2.getHead());slist.show();}}
