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

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

节点类：

class HeroNode {public int no;public String name;public String nickname;public HeroNode next; //指向下一个节点//构造器public HeroNode(int no, String name, String nickname) { = no;this.name = name;this.nickname = nickname;}//为了显示方法，重写toString方法@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + ''' +", nickname='" + nickname + ''' +"}";}
}

 创建节点对象：

    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.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero3);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero2);//测试修改节点的代码HeroNode newHeroNode = new HeroNode(2, "李逵", "黑旋风");//显示链表singleLinkedList.list();
}

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

    /*** 获取到单链表节点的个数(如果是带头节点的链表，需求不统计头节点)** @param head 链表的头节点* @return 返回的就是有效节点的个数*/public static int getLength(HeroNode head) {if ( == null) {// 空链表return 0;}int Length = 0;//定义一个辅助变量HeroNode cur = ;while (cur != null) {Length++;cur = ;//遍历}return Length;}
}

2.倒数索引输出响应的节点：

    /*** 查找单链表中的倒数第k个节点【新浪面试题】** @param index 链表倒数的索引值* @return 返回一个链表节点*/public static HeroNode reverse_index(HeroNode head, int index) {HeroNode Temp = ;HeroNode cur = ;int length = 0;if ( == null) {System.out.println("链表为空，无元素查找");length = 0;}while (true) {cur = ;++length;if (cur == null) {break;}}if (index > length) {System.out.println("您输入的索引越界，请重新输入~");} else if (index > 0 && index <= length) {for (int i = 1; i < length - index + 1; i++) {Temp = ;}} else {System.out.println("您输入的索引有误，请重新输入~");}return Temp;}

3. 将单链表反转

（头插法）算法思想：设置临时节点头 reverseHead ，遍历链表，每遍历一个元素(cur)将元素插入到临时链表头的下一个节点位置，即( = cur)，然后将cur继续向后移动，直至cur==null;

核心代码：

            next = ; //暂时保存当前节点的下一个节点，以便后面使用
            = ; //将cur的下一个节点指向新的链表的最前端
            = cur; //将临时节点头，指向最新的节点
            cur = next; //让cur后移一位

    public static void reserveList(HeroNode head) {HeroNode reverseHead = new HeroNode(0, "", "");HeroNode next = null;HeroNode cur = ; == null){System.out.println("链表为空，不需要必反转~");}ext == null){System.out.println("链表为单节点链表，不需要反转~");}while(cur != null){next = ; //暂时保存当前节点的下一个节点，以便后面使用 = ; //将cur的下一个节点指向新的链表的最前端 = cur; //将临时节点头，指向最新的节点cur = next; //让cur后移一位}
//         = reverseHead;  //先将临时头节点加入链表
//         = ; //再将头节点跳跃临时节点// 上两行代码等于下面代码 = ; //直接将临时链表头取代}

单链表反转主要包括以下几种常用的方法：

1. 迭代反转法：从当前链表的第一个结点开始遍历整个链表，期间逐个改变所遍历的结点的指针域，令其指向前一个结点。

2. 递归反转法：这种方法是从链表的尾节点开始，依次向前遍历，遍历过程依次改变各节点的指向，即另其指向前一个节点。

3. 头插法：这种方法是创建一个节点作为新的头节点。遍历整个单向链表，每遍历到一个结点便把该结点移至新的头结点的下一个结点，直到到遍历结束。然后将新的头节点再替换为源头结点。

4. 原地逆置法：这种方法通常用于反转不带头节点的链表。

4.将链表逆序输出（百度面试题）

提示：可以使用栈的相关知识

    public static void reserveShow(HeroNode head) {HeroNode tempHead = new HeroNode(0, " ", " ");HeroNode next = null;HeroNode cur = ;if ( == null) {System.out.println("链表为空，不需要必反转~");}if ( == null) {System.out.println("链表为单节点链表，不需要反转~");}Stack<HeroNode> stack = new Stack<>();while (cur != null) {//循环遍历当前链表，依次入栈next = ;stack.add(cur);cur = next;}while (stack.size() > 0) {//依次出栈遍历System.out.println(stack.pop());}}

控制台输出如下：