单链表之大厂面试题

上一节已经更新了单链表的基本实现，和特征。接下来将分享一些笔试中大厂对单链表进行笔试时，会出的一些面试题。应用场景是上一节的代码里面的，这里将贴出具体的实现方法的代码，想要全部代码，可以看上一篇文章的链接:
https://www.jianshu.com/p/6d99b791d758

下面将展示一些面试题:
1.求单链表中节点的个数(代表头的和不带表头的)
2.查找单链表中的倒数第K个节点。
3.单链表的反转。
4.从尾到头打印单链表。
5.合并两个有序的单链表，合并后依然有序。

1.求单链表中节点的个数(代表头的和不带表头的)

/**
         * 新浪面试题锦集:
         * 1.求单链表中有效节点的个数
         */
        public int getLength(HeroNode head) {

            HeroNode temp = head;
            int length = 0;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                length++;
                temp = temp.next;
            }
            return length;
        }

2.查找单链表中的倒数第K个节点。

/**
         * 找到链表的最后第K个节点
         * <p>
         * 思路:
         * 1.先遍历过去单链表的总长度
         * 2.将总长度size减去K，得到Index
         * 3.从表头开始遍历到index，此时就是链表的倒数第K个节点了。
         * @return
         */
        public HeroNode getLastIndexLinkedList(HeroNode head,int k) {
            int length = getLength(head);
            int index = length - k;
            if(length == 0){
                System.out.println("该链表为null");
                return null;
            }else if(k<0 || index < 0){
                System.out.println("这个k值输入有误");
                return null;
            }else if(index>length){
                System.out.println("没有找到该节点");
                return null;
            }

            HeroNode temp=head;
            for(int i=0;i<=index;i++){
                temp=temp.next;
            }
            System.out.println(temp);
            return temp;
        }

3.单链表的反转。

image.png

/**
         * 腾讯面试题
         * 将单链表进行反转
         */
        public HeroNode reversetLinkedList(HeroNode head) {

            if(head.next==null || head.next.next==null){
                System.out.println("当前链表为空或者只有一个，不需要反转");
            }

            HeroNode reversetList = new HeroNode(0, "", "");
            HeroNode next=null;
            HeroNode cur=head.next;

            while (cur!=null){
               next=cur.next;
               cur.next=reversetList.next;
               reversetList.next=cur;
               cur=next;
            }
            return reversetList;
        }

4.从尾到头打印单链表。 image.png

/**
         * 从尾到头打印单链表(百度)
         * 思路: 1.先将链表反转，然后再打印(会破坏原来的结构，不建议)
         *         2.使用栈来实现。
         */
        public void printLinkedList(HeroNode head){

            if(head==null || head.next==null){
                System.out.println("该链表为空");
                return;
            }
            Stack<HeroNode> heroNodes = new Stack<>();
            HeroNode temp = head;
            while (temp.next!=null){

                if(temp.next!=null){
                    heroNodes.push(temp.next);
                }
                temp=temp.next;
            }

            while (heroNodes.size()!=0){
                System.out.println(heroNodes.pop());
            }
        }