链表中倒数第K个结点

柔情只为你懂 2022-03-25 15:29 218阅读 0赞

# [链表中倒数第K个结点][K] #

## 题目描述 ##

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

1 /*
     2 public class ListNode {
     3     int val;
     4     ListNode next = null;
     5 
     6     ListNode(int val) {
     7         this.val = val;
     8     }
     9 }*/
    10 public class Solution {
    11 
    12 
    13 public ListNode FindKthToTail(ListNode head,int k) {
    14         if(head==null||k<=0){
    15             return null;
    16         }
    17         ListNode pre=head;
    18         ListNode last=head;       
    19         for(int i=1;i<k;i++){
    20             if(pre.next!=null){
    21                 pre=pre.next;
    22             }else{
    23                 return null;
    24             }
    25         }
    26         while(pre.next!=null){
    27             pre = pre.next;
    28             last=last.next;
    29         }
    30         return last;
    31     }
    32 }

思路（转发加个人思路）

第K个节点也就是从最后一个到某个距离为K的节点的过程。

所以等于是俩个人从起点走路，A始终比B领先K步，当A走了K-1步（K-1个结点）时，B处于起点位置（这里的长度和节点个数是一个概念）。

之后，A和B同步走，但A走到终点的时候，B也就走到了距离终点（距离A位置）的K个距离（也就是题目的倒数第K个节点）

距离：

五个节点 1 2 3 4 5   K=3

令指针pre和last都指向1位置，只要节点个数大于K，pre走了2步，到达3的位置，此时pre和last的结点距离为3，然后同步走，但pre走到了5的位置，last同步走到了3的位置，那么此时last的位置的结点就是整个链表的倒数第K个结点

posted @ 2018-08-06 20:23 [Octopus22][] 阅读( ...) 评论( ...) [编辑][Link 1] 收藏

[K]: https://www.cnblogs.com/Octopus-22/p/9432679.html
[Octopus22]: https://www.cnblogs.com/Octopus-22/
[Link 1]: https://i.cnblogs.com/EditPosts.aspx?postid=9432679