单链表常见的4道笔试题（Java版）

Z时代
2024-01-10
分类：综合

java

单链表中有效节点的个数

思路分析：

如果是带头节点的链表，不需要统计头节点。也就是说该链表的长度。
判断该链表是否为空，如果为空，则直接返回 0 ；
定一个变量length，用来记录节点的个数；
不为空，用一个临时变量指向头结点的下一个位置，
遍历该链表，只要data不为空，length加一。直到temp的下一位为空为止。
返回该变量

代码实现：

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;
}

查找单链表中的倒数第k个结点

思路分析：findLastIndexNode（Node node , int index）

先判断该链表是否为空，为空则返回null;
不为空，则先进行遍历，输出链表的总长度
定以一个临时变量temp用来进行遍历操作，temp是从head头部下一个节点开始的
定义一个size用来存储链表的长度；
只要temp不为空，size就加一，直到遍历完整个链表
index的合法性判断，不能小于等于0或大于链表总长度
再for循环到size-index次，将temp指向目标位置；
返回该节点

代码实现：

public HeroNode findLastIndexNode(Node node，int index) {
    // 判断链表是否为空，
    if (node == null) {
        return null;
    }
    // 不为空，则先进行遍历，输出链表的总长度
    // 定以一个临时变量temp用来进行遍历操作，
    HeroNode temp = head.next;//从链表头部的下一个开始
    // 定义一个size用来存储链表的长度
    int size = 0;
    while (temp != null) {// temp下一个节点还有值
        size++;
        temp = temp.next;//指向下一个节点继续
    }
    System.out.println(size);
    // 得到链表的总长度size后，我们只需遍历size-index次即可得到第K个元素
    HeroNode cur = head.next;
    // 保证输入的index是有效的
    if(index <= 0 || index > size){
        return null;
    }
    for(int i = 0; i< size-index;i++){
        cur = cur.next;
    }
    return cur;
}

单链表的反转

思路分析：

先定义一个新的头节点，reverseHead
从头到尾去遍历原来的链表，每遍历一个节点，将其取出，放到reverseHead节点的后面
将原来的头部.next指向reverseHead.next

代码实现：

public static void reverseLinkedList(HeroNode node) {
    // 1. 判断所给的链表的长度是0或是1不用反转
    if(node.next == null || node.next.next == null){
        return;
    }
    //2. 定义一个新的头节点，reverseHead
    HeroNode reverseHead = new HeroNode(0,"","");
    //3. 从头到尾去遍历原来的链表，每遍历一个节点，将其取出，放到reverseHead节点的后面
    HeroNode cur = node.next; // 临时变量用来进行遍历操作
    HeroNode next = null; //用来存储当前节点的下一个节点的位置
    while(cur != null) {
        // 从右往左进行插入，
        next = cur.next; // 
        cur.next = reverseHead.next; // 如果temp此时是节点2，那么reverseHead.next是节点1，我们先让节点2的下一位指向节点1
        reverseHead.next = cur; //让新链表的头结点指向取出来的节点。把temp插到reverseHead后面
        cur = next; // 继续
    }
    //4. 将原来的头部.next指向reverseHead.next
    node.next = reverseHead.next;
}s

从尾到头打印单链表

方式1：反向遍历

先反转再遍历，会破坏链表的结构

方式2：Stack栈

思路分析：

利用栈，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
先判断所给链表是否为空，为空直接返回
不为空，创建一个栈，定义一个临时变量遍历链表，将节点压栈
只要栈不为空，就先进后出的弹栈pop()

代码实现：

public static void reversePrint2(HeroNode node){
    //1.
    if(node.next == null){
        return;
    }
    //2.
    HeroNode cur = node.next;
    Stack<HeroNode> stack = new Stack<HeroNode>();
    while(cur != null){
        stack.push(cur);
        cur = cur.next;
    }
    // 3.
    while(!stack.empty()){ //或者stack.size()>0
        System.out.println(stack.pop());
    }
}