上一篇给大家介绍了单链表的使用,本篇给大家分析一下单链表常见的面试题(全是干货)

单链表中有效数据

效果图:

最终有效数据结果为: 5

代码实现:

//单链表有效个数
    public int linkedLength(HeroNode head) {

        int length = 0;

        while (head.next != null) {
            length++;
            head = head.next;
        }
        return length;
    }
复制代码

总结:

传入头结点,循环头节点中所有数据,通过 length 标识记录下来即可

单链表数据反转

效果图:

第一次分析:

1.遍历头节点所有数据
2.通过一个辅助reverseHead头节点,将节点数据依次添加到辅助节点reverseHead上

我这么说可能优点生硬.看图说话!

辅助图:

第二次分析:

1.要想完成单链表反转,那么单链表中的有效元素就必须 >= 2,否则只有一个元素也不需要反转
2.最后将原来头结点指向reverseHead的下一个位置完成单链表的反转

具体实现:

    //单链表反转
    public void reversal(HeroNode head) {
        //链表个数<=0 不能反转
        if (head.next == null || head.next.next == null) {
            return;
        }

        //定义辅助遍历.帮我遍历原来链表
        HeroNode temp = head.next;

        //指向当前节点的下一个节点
//        HeroNode next = null;

        //反转的节点
        HeroNode reverseHead = new HeroNode(0, "", "");

        //遍历原来链表,每遍历一次,放入到reverseHead中
        while (temp != null) {
            //保存当前节点的下一个节点(next为辅助节点)
            HeroNode next = temp.next;

            //将 cur 的下一个节点指向新的链表的头结点
            temp.next = reverseHead.next;

            //将 cur 连接到新的链表上
            reverseHead.next = temp;

            //让 cur 指向下一个节点
            temp = next;
        }

        //将 head.next 指向 reverseHead.next
        head.next = reverseHead.next;
    }
复制代码

使用:

        linkedList.add(new HeroNode(1, "宋江", "及时雨"));
        linkedList.add(new HeroNode(5, "秦明", "霹雳火"));
        linkedList.add(new HeroNode(6, "柴进", "小旋风"));
        linkedList.add(new HeroNode(3, "吴用", "智多星"));
        linkedList.add(new HeroNode(2, "李逵", "黑旋风"));
        
         linkedList.show();

        linkedList.reversal(linkedList.head);

        System.out.println("反转后的结果为:");
        linkedList.show();  
复制代码

运行结果为:

HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=5, name='秦明', nickName='霹雳火'}
HeroNode{no=6, name='柴进', nickName='小旋风'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=2, name='李逵', nickName='黑旋风'}
反转后的结果为:
HeroNode{no=2, name='李逵', nickName='黑旋风'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=6, name='柴进', nickName='小旋风'}
HeroNode{no=5, name='秦明', nickName='霹雳火'}
HeroNode{no=1, name='宋江', nickName='及时雨'}
复制代码