12.获得单链表倒数第k个结点

目录介绍

  • 01.题目要求
  • 02.问题分析
  • 03.实例代码
  • 04.改进代码
  • 05.加强代码

01.题目要求

  • 输入一个链表，输出该链表中倒数第k个结点

02.问题分析

2.1 一句话概括

  • 两个指针一个指针p1先开始跑，指针p1跑到k-1个节点后，另一个节点p2开始跑，当p1跑到最后时，p2所指的指针就是倒数第k个节点。
  • 或者说：链表中倒数第k个节点也就是正数第(L-K+1)个节点

2.2 解题思路

  • 先将整个链表从头到尾遍历一次，计算出链表的长度size，得到链表的长度之后，就好办了，直接输出第(size-k)个节点就可以了（注意链表为空，k为0，k为1，k大于链表中节点个数时的情况）

03.实例代码

  • 代码如下
    public class LinkList {
    public Node head;
    public Node current;
    
    class Node {
        //注：此处的两个成员变量权限不能为private，因为private的权限是仅对本类访问。
        int data; //数据域
        Node next;//指针域
        public Node(int data) {
            this.data = data;
        }
    }
    
    //方法：向链表中添加数据
    public void add(int data) {
        //判断链表为空的时候
        if (head == null) {//如果头结点为空，说明这个链表还没有创建，那就把新的结点赋给头结点
            head = new Node(data);
            current = head;
        } else {
            //创建新的结点，放在当前节点的后面（把新的结点合链表进行关联）
            current.next = new Node(data);
            //把链表的当前索引向后移动一位
            current = current.next;   //此步操作完成之后，current结点指向新添加的那个结点
        }
    }
    
    
    //index代表的是倒数第index的那个结点
    public int findLastNode(int index) {  
        //第一次遍历，得到链表的长度size
        if (head == null) {
            return -1;
        }
        current = head;
        while (current != null) {
            size++;
            current = current.next;
        }
        //第二次遍历，输出倒数第index个结点的数据
        current = head;
        for (int i = 0; i < size - index; i++) {
            current = current.next;
        }

        return current.data;
    }
}
  • 测试代码
    public void test() {
    LinkList list = new LinkList();
    //向LinkList中添加数据
    for (int i = 0; i < 10; i++) {
        list.add(i);
    }
    list.findLastNode(2);// 获取单链表倒数第index的那个结点
}

04.改进代码

  • 如果不允许你遍历链表的长度，该怎么做呢？改进思路：
    • 这里需要声明两个指针：即两个结点型的变量first和second，首先让first和second都指向第一个结点，然后让second结点往后挪k-1个位置，此时first和second就间隔了k-1个位置，然后整体向后移动这两个节点，直到second节点走到最后一个结点的时候，此时first节点所指向的位置就是倒数第k个节点的位置。时间复杂度为O（n）
  • 改进后代码
    public Node findLastNode(Node head, int index) {
    if (node == null) {
        return null;
    }
    Node first = head;
    Node second = head;
    //让second结点往后挪index个位置
    for (int i = 0; i < index; i++) {
        second = second.next;
    }
    //让first和second结点整体向后移动，直到second结点为Null
    while (second != null) {
        first = first.next;
        second = second.next;
    }
    //当second结点为空的时候，此时first指向的结点就是我们要找的结点
    return first;
}

05.加强代码

  • 考虑k大于链表中结点个数时的情况时，抛出异常。看似已经实现了功能，其实还不够健壮:
    • 要注意k等于0的情况；如果k大于链表中节点个数时，就会报空指针异常，所以这里需要做一下判断。
  • 代码如下所示
    public Node findLastNode(Node head, int k) {
    if (k == 0 || head == null) {
        return null;
    }

    Node first = head;
    Node second = head;

    //让second结点往后挪k-1个位置
    for (int i = 0; i < k - 1; i++) {
        System.out.println("i的值是" + i);
        second = second.next;
        if (second == null) { //说明k的值已经大于链表的长度了
            //throw new NullPointerException("链表的长度小于" + k); //我们自己抛出异常，给用户以提示
            return null;
        }
    }

    //让first和second结点整体向后移动，直到second走到最后一个结点
    while (second.next != null) {
        first = first.next;
        second = second.next;
    }

    //当second结点走到最后一个节点的时候，此时first指向的结点就是我们要找的结点
    return first;
}
贡献者: yangchong211