单链表相关习题

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

设置一个临时变量来当作计数器。然后对整个链表进行遍历来数出有效节点的个数。

    public int getLength() {
        int length = 0;
        Student temp = head;

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

也可以直接使用whil来判断进行条件。

    public int getLength() {
        int length = 0;
        Student temp = head;

        while (temp.next != null) {
            length ++;
            temp = temp.next;
        }
        return length;
    }

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

解决这个问题的思路为
1.通过获得整个链表的节点数size
2.然后减去要找的第k个节点
3.得到需要将链表遍历的次数
4.然后使用一个temp节点来保存遍历后的目的节点
5.最后将temp返回。

    //从头节点的next开始
    public Student findLastIndexNode(int num) {

        Student temp = head.next;
        int size = getLength();

        if(temp == null) {
            return null;
        }

        if(num > size || num <= 0) {
            return null;
        }

        for (int i = 0; i < size - num; i++) {
            temp = temp.next;
        }

        return temp;
    }

    // 从头节点开始
    public Student findLastIndexNode(int num) {

        Student temp = head;
        int size = getLength();

        if(temp.next == null) {
            return null;
        }

        if(num > size || num <= 0) {
            return null;
        }

        for (int i = 0; i < size - num + 1; i++) {
            temp = temp.next;
        }

        return temp;
    }

3. 单链表的反转

1.首先创建一个反转的头节点
2.然后再定义一个临时系欸但来帮助我们遍历原来的链表
3.每遍历一个节点，就取出一个节点插入到反转头节点的后面
4.最后将反转头节点的next赋给原来的head的next域

   public void revrese() {
       if(head.next == null || head.next.next == null) {
           return;
       }

       Student temp = head.next;
       Student next = null;
       Student reverseList = new Student("",0);

       while (temp != null) {
           next = temp.next;
           temp.next = reverseList.next;
           reverseList.next = temp;
           temp = next;
       }
       
       head.next = reverseList.next;
   }

4. 从尾到头打印单链表

这里我们使用栈的特性，先进后厨的原则来遍历链表。

   public void reversePrint() {
       if (head.next == null) {
           return;
       }

       Stack<Student> studentStack = new Stack<Student>();
       Student temp = head.next;

       while (temp != null) {
           studentStack.push(temp);
           temp = temp.next;
       }
       
       while (studentStack.size() > 0){
           System.out.println(studentStack.pop());
       }
   }