单链表面试题

Alan 528 2022-09-05
求单链表中有效节点的个数

入参:头节点,返回:节点个数,思路:首先判断链表长度为0的情况:如果头节点的next为空,表示空的单项链表。订单计数器,然后循环链表,如果头节点的next不为空,计数器+1。最后返回计数器即可。

/**
 * 获取单链表的长度
 * @param head 头节点
 * @return 长度
 */
public int getLength(HeroNode head) {
    if (head.next == null) {
        return 0;
    }
    //定义temp,不统计头节点。
    HeroNode temp = head.next;
    //定义length
    int length = 0;
    while (temp != null) {
        length++;
        temp = temp.next;
    }
    return length;
}
查找单链表中的第K个节点

入参:头节点,返回:节点个数,思路:找到链表的有效节点的个数length,从链表的第一个元素开始遍历,遍历length - index次就可以了。

/**
 * 查找单链表中的第K个节点
 */
public static HeroNode getK(HeroNode head, int index) {
    //如果无下一个节点,返回空
    if (head.next == null) {
        return null;
    }
    //获取链表节点长度
    int length = getLength(head);
    if (index <= 0 || index > length) {
        return null;
    }
    //订单temp
    HeroNode temp = head.next;
    for (int i = 0; i < length - index; i++) {
        temp = temp.next;
    }
    return temp;
}
单链表的反转

思路:1.先定义一个节点reverseNode = new HeroNode(); 2.从头到尾遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表的最前端。3.原来的链表的head.next = reverseHead.next;

/**
 * 反转链表
 * @param head
 */
public static void reverse(HeroNode head) {
    //定义cur
    HeroNode cur = head.next;
    //定义next
    HeroNode next = null;
    //定义reverseNode
    HeroNode reverseHead = new HeroNode(0, "", "");
    while (cur != null) {
        next = cur.next;
        cur.next = reverseHead.next;
        reverseHead.next = cur;
        cur = next;
    }
    head.next = reverseHead.next;
}
从尾到头打印单链表

思路:1.先将单链表反转操作,然后遍历,但是这么做不可取因为会破环单链表的结构。2.利用栈的数据结构,将各个节点压入到栈中,利用栈的先进后出的特点,就实现了逆序打印的效果。

public static void reverseSoutHeroNode(HeroNode head) {
    if (head.next == null) {
        return;
    }
    //stack
    Stack<HeroNode> stack = new Stack<>();
    HeroNode temp = head.next;
    while (temp != null) {
        stack.push(temp);
        //temp下移
        temp = temp.next;
    }
    while (!stack.isEmpty()){
        System.out.println(stack.pop());
    }
}

# 数据结构 # 链表