[数据结构与算法]数据结构——单向链表练习(java)

单向链表的实现请参照前一篇文章内容：https://blog.csdn.net/qq_52597311/article/details/120518537?spm=1001.2014.3001.5501

1)求单链表中有效节点的个数
2)查找单链表中的倒数第k个结点
3)单链表的反转
4)从尾到头打印单链表?

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

思路：定义一个变量length来记录结点个数，除去头指针之外，遍历链表，每遍历一个结点，length++

private static int getLength(Student head) {
        if (head.next == null) {//空链表
            return 0;
        }
        int length = 0;
        //定义一个辅助的变量,没有统计头节点
        Student cur = head.next;
        while (cur != null) {
            length++;
            cur = cur.next;//遍历
        }
        return length;
    }

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

思路：

1. 编写一个方法接收head节点，同时接收一个index
2. index表示是倒数第index个节点
3. 先把链表从头到尾遍历一遍，得到链表的总的长度 调用getLength()
4. 得到size后，从链表的第一个开始遍历(size-index)个?
5. 如果找到了，则返回该节点，否则返回空

private static HeroNode findLastIndexNode(HeroNode head, int index) {
        //判断链表是否为空
        if (head.next == null) {
            return null;
        }
        //第一次遍历得到节点的个数
        int size = getLength(head);
        //第二次遍历 size-index 位置，就是倒数第k个节点
        //先做一个index的校验
        if (index <= 0 || index > size) {
            return null;
        }
        //定义一个辅助变量,for循环定位到倒数的index
        HeroNode cur = head.next;//3 //3-1=2
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }

3.单链表的反转

private static void reversetList(Student head) {
        //如果当前链表为空，或者只有一个节点，无需反转,直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }
        //定义一个辅助指针(变量),帮助遍历原来的链表
        Student cur = head.next;
        Student next = null;//指向当前节点[cur]的下一个节点
        Student reverseHead = new Student(0, "");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
        while (cur != null) {
            next = cur.next;//先暂时保存当前节点的下一个节点,因为后面需要使用
            cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
            reverseHead.next = cur;//将cur连接到新的链表上
            cur = next;//让cur后移
        }
        //将head.next指向reverseHead.next,实现单链表的反转
        head.next = reverseHead.next;
    }

4.从尾到头打印单链表?

法一：
思路：
利用栈的数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果?

private static void reversePrint(Student head) {
        if (head.next == null) {
            return;//空链表
        }
        //创建一个栈，将各个节点压入栈中
        Stack<Student> stack = new Stack<>();
        Student cur = head.next;
        //将链表的所有节点压入栈中
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;//后移
        }
        //将栈中的节点进行打印，pop出栈
        while (stack.size() > 0) {
            System.out.println(stack.pop());//stack的特点是先进后出
        }
    }

?法二：

思路：

1. 可先利用临时变量s1遍历到链表的尾部，先输出尾部
2. 利用s2找到s1的前一个结点,条件为s2.next!=s1
3. 找到后输出当前结点，再将当前结点赋值给s1
4. 不输出头结点，循环条件为s1!=head.next

private static void reversePrint1(Student head) {
        if (head.next == null) {
            return;
        }
        Student s1 = head;//辅助指针
        Student s2 = null;//辅助指针
        while (s1.next != null) {//不输出头节点
            s1 = s1.next;//找到尾结点
        }
        //先输出尾结点
        System.out.println(s1);
        while (s1 != head.next) {
            s2 = head;//每次都要重置
            while (s2.next != s1) {//寻找s1的前一个结点
                s2 = s2.next;
            }
            //找到后输出
            System.out.println(s2);
            //将当前结点赋值给s1
            s1 = s2;
        }
    }