JAVA数据结构与算法——单链表面试题（新浪、百度、腾讯）_综合

单链表的常见面试题

求单链表中有效节点的个数
查找单链表中倒数第k个节点（新浪）
单链表的反转（腾讯）
从尾到头打印单链表（百度，要求方式一：反向遍历。方式二：stack栈）

例题1：求有效节点个数

思路：

方法：获取有效节点的个数（如果是带头结点的链表，需要不统计头结点）
head是头结点，length是有效节点个数

关键代码实现：

	public static int getLength(HeroNode head) {if (head.next == null) {// 空链表判断return 0;}int length = 0;// 计数器HeroNode cur = head.next;// 辅助变量while (cur != null) {// 未统计头结点length++;cur = cur.next;// 遍历}return length;}

例题2：查找单链表中倒数第K个节点

思路：

编写一个方法，接受head节点，同时接收一个index
index表示倒数第index个节点
先把链表从头至尾遍历，得到链表总长度getLength
得到size后，我们从链表第一个开始遍历(size-index)个
如果找到了，就返回该节点，否则返回null

关键代码实现：

public static HeroNode findLastIndexNode(HeroNode head, int index) {// 判空：链表为空，返回nullif (head.next == null) {return null;}// 第一次遍历：获取链表长度int size = getLength(head);// 第二次遍历：(size-index)就是我们倒数第index个节点// 数据校验if (index <= 0 || index > size) {return null;}// 辅助变量HeroNode cur = head.next;// for循环定位for (int i = 0; i < size - index; i++) {cur = cur.next;}return cur;}

例题3：单链表的反转

思路：（注：反转节点，不单单是数据）

先定义一个新节点（reverseHead = new HeroNode（））
从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并且放在新链表的最前端
原来的链表的head.next = reverseHead.next

代码实现：

	// 将单链表进行反转public static void reverseList(HeroNode head) {// 判断if (head.next == null || head.next.next == null) {return;}// 辅助变量（帮助遍历原来的链表）HeroNode cur = head.next;HeroNode next = null;// 指向当前节点[cur]的下一个节点HeroNode reverseHead = new HeroNode(0, "", "");// 新节点// 遍历原来的链表while (cur != null) {next = cur.next;// 暂时保存当前节点的下一个节点cur.next = reverseHead.next;// 将cur的下一个节点指向新的链表的头部节点reverseHead.next = cur;//将cur链接到新的链表上cur = next;// 后移}// 将head.next指向reversHead.next，实现反转head.next = reverseHead.next;}

例题4：从尾到头打印单链表

思路:

方式1：先将单链表进行反转，在遍历，如例题3，但是不建议

方式2：可以利用“栈”，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果

栈知识补充：先入后出

测试代码（栈）

package com.jun._3_linkedlist;import java.util.Stack;/*** 测试栈的使用* @author jun**/
public class Test_Stack {public static void main(String[] args) {Stack<String> stack = new Stack();//入栈stack.add("jack");stack.add("tom");stack.add("smith");//出栈while(stack.size()>0) {System.out.println(stack.pop());}}}

栈输出：

smith
tom
jack

代码实现：

	// 逆序打印public static void reversePrint(HeroNode head) {if (head.next == null) {// 判空return;}// 创建栈，将各个节点压入栈中Stack<HeroNode> stack = new Stack<HeroNode>();HeroNode cur = head.next;// 将链表所有节点压入while (cur != null) {stack.push(cur);cur = cur.next;// cur后移，压入下一个节点}// 遍历栈中节点while (stack.size() > 0) {System.out.println(stack.pop());// 先入后出}}

附完整代码

package com.jun._3_linkedlist;import java.util.Stack;/*** 通过单链表来管理英雄人物* * @author jun**/
public class SingleLinkedListDemo {public static void main(String[] args) {// 创建节点HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");HeroNode hero3 = new HeroNode(3, "吴用", "智多星");HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");// 创建链表SingleLinkedList singleLinkedList = new SingleLinkedList();// 按照方式一加入：
//		singleLinkedList.add(hero1);
//		singleLinkedList.add(hero2);
//		singleLinkedList.add(hero3);
//		singleLinkedList.add(hero4);// 按照方式二加入：singleLinkedList.add2(hero1);singleLinkedList.add2(hero4);singleLinkedList.add2(hero2);singleLinkedList.add2(hero3);singleLinkedList.add2(hero3);// 显示singleLinkedList.list();// 修改HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~~~~");System.out.println("修改后：");singleLinkedList.update(newHeroNode);singleLinkedList.list();// 删除singleLinkedList.dele(1);System.out.println("删除后：");singleLinkedList.list();// 获取有效节点的个数System.out.println("有效节点的个数=" + getLength(singleLinkedList.getHead()));// 测试倒数第k个节点HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 1);System.out.println(res);HeroNode res1 = findLastIndexNode(singleLinkedList.getHead(), 2);System.out.println(res1);// 测试单链表的反转System.out.println("测试链表：");singleLinkedList.list();System.out.println("反转之后：");reverseList(singleLinkedList.getHead());singleLinkedList.list();//逆序打印System.out.println("逆序打印:");reverseList(singleLinkedList.getHead());singleLinkedList.list();}// 逆序打印public static void reversePrint(HeroNode head) {if (head.next == null) {// 判空return;}// 创建栈，将各个节点压入栈中Stack<HeroNode> stack = new Stack<HeroNode>();HeroNode cur = head.next;// 将链表所有节点压入while (cur != null) {stack.push(cur);cur = cur.next;// cur后移，压入下一个节点}// 遍历栈中节点while (stack.size() > 0) {System.out.println(stack.pop());// 先入后出}}// 将单链表进行反转public static void reverseList(HeroNode head) {// 判断if (head.next == null || head.next.next == null) {return;}// 辅助变量（帮助遍历原来的链表）HeroNode cur = head.next;HeroNode next = null;// 指向当前节点[cur]的下一个节点HeroNode reverseHead = new HeroNode(0, "", "");// 新节点// 遍历原来的链表while (cur != null) {next = cur.next;// 暂时保存当前节点的下一个节点cur.next = reverseHead.next;// 将cur的下一个节点指向新的链表的头部节点reverseHead.next = cur;// 将cur链接到新的链表上cur = next;// 后移}// 将head.next指向reversHead.next，实现反转head.next = reverseHead.next;}// 查找单链表中倒数第K个节点/*** 思路： 1、编写一个方法，接受head节点，同时接收一个index 2、index表示倒数第index个节点* 3、先把链表从头至尾遍历，得到链表总长度getLength 4、得到size后，我们从链表第一个开始遍历(size-index)个* 5、如果找到了，就返回该节点，否则返回null*/public static HeroNode findLastIndexNode(HeroNode head, int index) {// 判空：链表为空，返回nullif (head.next == null) {return null;}// 第一次遍历：获取链表长度int size = getLength(head);// 第二次遍历：(size-index)就是我们倒数第index个节点// 数据校验if (index <= 0 || index > size) {return null;}// 辅助变量HeroNode cur = head.next;// for循环定位for (int i = 0; i < size - index; i++) {cur = cur.next;}return cur;}// 方法：获取有效节点 的个数（如果是带头结点的链表，需要不统计头结点）// head是头结点，length是有效节点个数public static int getLength(HeroNode head) {if (head.next == null) {// 空链表判断return 0;}int length = 0;// 计数器HeroNode cur = head.next;// 辅助变量while (cur != null) {// 未统计头结点length++;cur = cur.next;// 遍历}return length;}}//管理英雄
class SingleLinkedList {// 初始化头结点private HeroNode head = new HeroNode(0, "", "");// 返回头结点public HeroNode getHead() {return head;}public void setHead(HeroNode head) {this.head = head;}// 第一种添加节点的方式// 思路：在没有考虑排名编号的时候。// 1、找到当前链表的最后节点// 2、将最后这个节点的next指向新的节点public void add(HeroNode heroNode) {// 辅助指针HeroNode temp = head;// 循环遍历while (true) {// 寻找链表的最后if (temp.next == null) {break;}// 未找到，将temp后移temp = temp.next;}temp.next = heroNode;}// 第二种添加英雄的方式，根据排名插入指定位置（如果有这个排名，则添加失败，并且给出提示）public void add2(HeroNode heroNode) { // 寻找的temp是位于添加位置的前一个节点HeroNode temp = head;boolean flag = false;// 标识编号是否存在，默认为falsewhile (true) {if (temp.next == null) {break;}if (temp.next.no > heroNode.no) { // 位置找到了，在temp后插入break;} else if (temp.next.no == heroNode.no) {// 编号存在flag = true;break;}temp = temp.next; // 后移，遍历}// 判断falg的值if (flag) {System.out.printf("编号%d存再，不能加入\n", heroNode.no);} else {// 插入链表中，temp后heroNode.next = temp.next;temp.next = heroNode;}}// 删除节点// 1.head不能动，因此需要temp辅助节点找到待删除节点的前一个节点。// 2.在比较的时候，是需要temp.next.no与待删除节点.no进行比较public void dele(int no) {HeroNode temp = head;boolean flag = false;// 标识是否找到待删除节点的前一个节点while (true) {if (temp.next == null) {// 已经到链表最后，退出break;}if (temp.next.no == no) {// 找到待删除节点的前一个节点tempflag = true;break;}temp = temp.next;// temp后移}// 判断flagif (flag) {// 找到temp.next = temp.next.next;} else {System.out.printf("要找的节点%d， 不存在\n", no);}}// 修改节点的信息public void update(HeroNode newHeroNode) {// 判空if (head.next == null) {System.out.println("链表为空");return;}// 找到需要的节点(辅助变量)HeroNode temp = head.next;boolean flag = false;while (true) {if (temp == null) {break;// 遍历完链表}if (temp.no == newHeroNode.no) {flag = true;break;}temp = temp.next;}// 根据flag找到是否要修改的点if (flag) {temp.name = newHeroNode.name;temp.nickname = newHeroNode.nickname;} else {// 没有找到System.out.printf("没有找到编号%d的节点，不能修改\n", newHeroNode.no);}}// 显示链表public void list() {if (head.next == null) {System.out.println("链表为空");return;}HeroNode temp = head.next;while (true) {// 判断if (temp == null) {break;}// 不为空，输出节点信息System.out.println(temp);// 将next后移temp = temp.next;}}
}//定义节点
class HeroNode {public int no;// 排名顺序public String name;// 名字public String nickname;// 别名public HeroNode next;// 指向下一个节点// 构造器public HeroNode(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}// 重写toString@Overridepublic String toString() {return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";}}

输出

编号3存再，不能加入
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]
修改后：
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=小卢, nickname=玉麒麟~~~~~]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]
删除后：
HeroNode [no=2, name=小卢, nickname=玉麒麟~~~~~]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]
有效节点的个数=3
HeroNode [no=4, name=林冲, nickname=豹子头]
HeroNode [no=3, name=吴用, nickname=智多星]
测试链表：
HeroNode [no=2, name=小卢, nickname=玉麒麟~~~~~]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]
反转之后：
HeroNode [no=4, name=林冲, nickname=豹子头]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=2, name=小卢, nickname=玉麒麟~~~~~]
测试逆序打印
HeroNode [no=2, name=小卢, nickname=玉麒麟~~~~~]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]