【剑指Offer题解：java】链表中倒数第K个节点

古城微笑少年丶 2023-01-10 13:16 72阅读 0赞

### 文章目录 ###

*   *  题目
     *  思路一
     *  思路二

## 题目 ##

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

## 思路一 ##

> 求倒数第k个，可以转换成求正数个数

![image.png][]

/** * 求倒数第k个，可以转换成求正数第多少个呢？ * @param head * @param k * @return */
        public CListNode FindKthToTail(CListNode head, int k) { 
            if (head == null || k < 0) return null;
            //求节点总数
            int sum = 0;
            CListNode temp = head;
            while (temp != null) { 
                sum++;
                temp = temp.next;
            }
            if (sum < k) return null;//总数小于倒数第k个
            //倒数第k个是正数第sum - k
            sum = sum - k;
            while (sum>0){ 
                head = head.next;//向后移动
                sum--;
            }
            return head;
        }

## 思路二 ##

> 使用快慢指针

使用如图的快慢指针，首先让快指针先行k步，然后让快慢指针每次同行一步，直到快指针指向空节点，慢指针就是倒数第K个节点。

![image.png][image.png 1]

public ListNode FindKthToTail(ListNode head,int k) { 
           if (head == null||k<0) return null;//考虑头指针为空的情况
            ListNode slow = head;//慢指针
            ListNode fast = head;//快指针
            //先将快指针移动到慢指针的后k个
            int index = k;
            while (index > 0) { 
                index--;
                if(fast!=null)fast = fast.next;//如果总长小于k则返回空
                else return null;
            }
            //现在将快慢指针同时向后移动，直到快指针移动到最后一个元素，此时慢指针所指的即为倒数第k个元素
            while (fast != null) { 
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }

[image.png]: /images/20221119/0e64a307fc3049f3b9db9c8b8e58d69a.png
[image.png 1]: https://img-blog.csdnimg.cn/img_convert/ccd70c8e0baf3d22871360ccdae43f7d.png