单链表反转及返回倒数第k个节点详解

单链表反转详解

1. 获取单链表有效节点的个数

• 思路分析（见源码）

• 源码及分析

//思路分析：
//简单：遍历单链表记录链表长度并返回

//获取单链表的有效节点的个数
    public static int getLength(HeroNode head) {
        //先判断该链表是否为空
        if (head.next == null) {
            return 0;
        }
        //定义一个辅助变量cur(即游标)，每次移动游标遍历链表
        HeroNode cur = head.next;
        //定义length保存链表的长度
        int length = 0;
        while (true) {
            if (cur == null) {
                break;
            }
            length++;
            cur = cur.next;
        }
        return length;

2. 返回单链表中倒数第k个节点

• 思路分析（见源码）
• 源码及分析

//编写方法返回链表中倒数第k个节点
    /**
     * @param head  链表头节点
     * @param index 倒数第index个节点的索引
     * @return
     */
    //思路分析：
    //1. 第一次遍历拿到链表的总长度length
    //2. 则可以确定倒数第index个节点所在的位置 length - index
    //3. 第二次再遍历 length - index 次则可以拿到倒数第k个节点
    public static HeroNode getLastIndexNode(HeroNode head, int index) {
        //先判断链表是否为空
        if (head.next == null) {
            return null;
        }
        //调用getLength方法拿到链表的长度
        int length = getLength(head);
        // 确认倒数第index个节点的顺数位置
        int size = length - index;
        //输入的实参校验
        if (index <= 0 || index > length) {
            return null;
        }
        //定义一个辅助变量帮助遍历
        HeroNode cur = head.next;
        for (int i = 0; i < size; i++) {
            cur = cur.next;
        }
        //循环结束后cur已经指向倒数第index个节点
        return cur;
    }

3. 单链表反转

• 思路分析
  1. 因为单链表之间仅仅依靠一条指针相连接，因此单链表的反转必须借助一条新链表作为辅助链表
  2. 遍历原先的链表，依次将每一个节点取下来挂载到新链表的最前端
  3. 其实质就是节点指针域的指向问题，节点对象并没有发生变化，稍微修改指针的指向，便可实现反转
  4. 详解看源码
• 源码及分析

//反转链表

    //思路分析：
    //1. 需要借助一个辅助链表
    //2. 依次遍历原链表，将原链表的每一个节点指向辅助链表的最前端
    //3. 再将辅助指向原链表
    public static void reverseLink(HeroNode head){
        //判断链表是否为空或者链表是否只有一个节点
        if (head.next == null || head.next.next == null){
            return;
        }
        //定义一个辅助指针cur,即变量，用于遍历链表
        HeroNode cur = head.next;
        //定义一个next指向cur的下一个节点，
        // 因为要先保存cur的下一个节点，然后再将cur指向新链表，否则链表会断
        HeroNode next = null;
        //定义一个新链表，用于辅助反转
        HeroNode newHead = new HeroNode();

        //遍历原先的链表,将每一个节点挂载到新链表上
        while (true){
            //判断链表是否遍历结束
            if (cur == null){
                break;
            }
            //next保存当前节点的下一个节点，
            // 因为如果不保存下一个节点，当当前节点指向新链表时，原先的链表将会断开
            next = cur.next;
            //当前节点的下一个节点指向新节点的第一个节点
            cur.next = newHead.next;
            //将当前节点挂载到新链表的最前边
            newHead.next = cur;
            //cur后移
            cur = next;
        }
        head.next = newHead.next;
    }

单链表反转及返回倒数第k个节点详解

原文：https://www.cnblogs.com/mx-info/p/14728435.html