测试类
/** * @author 兴趣使然黄小黄 * @version 1.0 * 测试链表 */ public class StudentListTest { public static void main(String[] args) { StudentNode node1 = new StudentNode("1", "黄小黄", 21); StudentNode node2 = new StudentNode("2", "懒羊羊", 21); StudentNode node3 = new StudentNode("3", "沸羊羊", 22); //创建单链表 录入数据 输出 StudentLinkedList list = new StudentLinkedList(); list.add(node1); list.add(node2); list.add(node3); System.out.println("遍历链表:"); list.showList(); //测试插入数据方法 StudentNode node5 = new StudentNode("5", "美羊羊", 19); StudentNode node4 = new StudentNode("4", "暖羊羊", 19); list.addByOrder(node5); list.addByOrder(node4); System.out.println("\n依次插入学号为5、4的学生后:"); list.showList(); //测试修改方法 System.out.println("\n测试修改方法:"); list.update(new StudentNode("1", "祢豆子", 10)); list.showList(); //测试删除方法 System.out.println("\n测试删除方法:"); list.delete("1"); list.delete("5"); list.showList(); } }
实现结果
遍历链表: StudentNode{no='1', name='黄小黄', age=21}--->StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22} 依次插入学号为5、4的学生后: StudentNode{no='1', name='黄小黄', age=21}--->StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}--->StudentNode{no='5', name='美羊羊', age=19} 测试修改方法: StudentNode{no='1', name='祢豆子', age=10}--->StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}--->StudentNode{no='5', name='美羊羊', age=19} 测试删除方法: 删除成功！ 删除成功！ StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19} Process finished with exit code 0
2 单链表的面试题
2.1 统计单链表中有效节点数量
/** * * @param head 头节点 * @return 返回有效节点个数 */ public static int getLength(StudentNode head){ if (head.next == null){ return 0; } int length = 0; StudentNode temp = head.next; while (temp != null){ length++; temp = temp.next; } return length; }
2.2 新浪–倒数第k个节点
查找链表中倒数第k个节点
思路分析：
- 编写一个方法，接收head头节点和index，index表示k；
- 链表从头到尾遍历，求出长度（链表节点个数）size；
- 从第一个节点，遍历size-length次，即可找到倒数第k个节点。
参考代码：
/** * 获取单链表中倒数第k个节点 * @param head 链表的头节点 * @param index 倒数第 k 个元素 * @return 返回倒数第 k 个元素，或者 null */ public static StudentNode findLastIndexNode(StudentNode head, int index){ //如果链表为空 if (head.next == null){ return null; } //得到链表的长度(节点个数) int size = getLength(head); //遍历 size-index次 得到倒数第index个节点 //数据校验 if (index <= 0 || index > size){ return null; } //遍历 StudentNode current = head.next; for (int i = 0; i < size - index; i++) { current = current.next; } return current; }
2.3 腾讯–单链表的反转
反转单链表
思路分析：
- 可以使用头插法；
- 以原链表为模板，每遍历一个节点，取出，并接在新链表的最前端；
- 原head头节点，指向新的节点；
- 直到遍历完为止。
参考代码：
/** * 头插法反转链表 * @param head 接收待反转的链表 * @return 返回一个反转后的新链表 */ public static StudentLinkedList reverseList(StudentNode head){ if (head.next == null){ return null; } StudentNode old = head.next; //用于遍历旧链表 //创建新链表，新链表根据原链表遍历得到 StudentLinkedList newList = new StudentLinkedList(); StudentNode newHead = newList.getHead(); //新链表的头节点 //遍历构造 boolean flag = true; //标记是否为第一次添加 while (old != null){ //头插法加入到新链表中 StudentNode newNode = new StudentNode(old.no, old.name, old.age); if(flag){ newHead.next = newNode; newNode.next = null; flag = false; }else { newNode.next = newHead.next; newHead.next = newNode; } old = old.next; } return newList; }
以上方式虽然可以实现链表的反转，但是是以返回一个新的反转链表的形式，并没有真正意义上实现原地反转，下面介绍另一种方式：
双指针:
/** * 双指针就地反转链表 * @param head 接收链表的头节点，方法中会将链表反转 */ public static void reverse(StudentNode head){ //如果当前链表为空 或者只有一个节点 直接返回即可 if (head.next == null || head.next.next == null){ return; } //辅助指针遍历原来的链表 StudentNode cur = head.next; //当前节点 StudentNode next = null; //指向cur的下一个节点 StudentNode reverseHead = new StudentNode("", "", 0); //遍历原来的链表，每遍历一个节点，就取出，放在新链表的最前端 while (cur != null){ next = cur.next; //暂时保存当前节点的下一个节点 cur.next = reverseHead.next; //讲cur下一个节点放在链表最前端 reverseHead.next = cur; cur = next; //cur后移动 } head.next = reverseHead.next; return; }
2.4 百度–逆序打印单链表
从尾到头打印单链表
方式一： 先将单链表反转，然后再打印。但是这样会破坏掉原有单链表的结构，而题目要求仅仅是打印，因此不建议！
方式二： 利用栈模拟
将单链表的各个节点压入栈中，利用栈先进后出的特点，实现逆序打印。
参考代码：
/** * 利用栈模拟 实现链表的逆序打印 * @param head 链表的头节点 */ public static void reversePrintList(StudentNode head){ if (head.next == null){ return; //空链表无法打印 } //创建栈模拟逆序打印 Stack<StudentNode> stack = new Stack<>(); //栈 StudentNode cur = head.next; //将链表的所有节点压入栈 while (cur != null){ stack.push(cur); cur = cur.next; } //逆序打印 while (!stack.empty()){ //出栈 System.out.println(stack.pop()); } return; }
