面试题22. 链表中倒数第k个节点

野性酷女 2023-03-14 13:24 15阅读 0赞

# 题目来源 #

[面试题22. 链表中倒数第k个节点][22. _k]  
[面试题 02.02. 返回倒数第 k 个节点 ][02.02. _ k _]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 常规解法 ##

先统计长度，再找准对应节点

class Solution {
        
        public ListNode getKthFromEnd(ListNode head, int k) {
        
            ListNode temp = head;
            int count = 1;
            while(temp != null){
        
                temp = temp.next;
                count++;
            }
    
    
            ListNode back = head;
            int p = 2;
            while(p != count - k + 1){
        
                back = back.next;
                p++;
            }
            
            return back;
        }
    }

public ListNode getKthFromEnd(ListNode head, int k) {
        
            ListNode slow=head,fast=head;
            int t = 0;
            while(fast!=null){
        
                if(t>=k) slow=slow.next;
                fast = fast.next;
                t++;
            }
            return slow;
        }

![在这里插入图片描述][20200518101126859.png]

## 双指针 ##

//思路：快慢指针法。消除长度差，当快指针到达末尾时，慢指针正好指向倒数第k个元素。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode getKthFromEnd(ListNode head, int k) {
        
            ListNode front = head;
            ListNode back = head;
            
            int i = 1;
            while (i <= k){
        
                if(front == null){
        
                    return null;
                }
    
                front = front.next;
                i++;
            }
    
            while(front != null){
        
                front = front.next;
                back = back.next;
            }
    
            return back;
        }
    }

![在这里插入图片描述][20200518100656456.gif]  
![在这里插入图片描述][20200518101132319.png]

## 递归 ##

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        private int count = 0;
        private ListNode node = null;
        public  ListNode getKthFromEnd(ListNode head, int k) {
        
            if (head == null || k <=  0){
        
                return null;
            }
    
    
            getKthFromEnd(head.next, k);
            count++;
            if (count == k){
        
                node = head;
            }
    
            return node;
        }
    }

[22. _k]: https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
[02.02. _ k _]: https://leetcode-cn.com/problems/kth-node-from-end-of-list-lcci/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20230312/59461f2842e4409699d4b084378e2d0f.png
[20200518101126859.png]: /images/20230312/8d3bdc0324ee4678a667d8e8cbd6ecf4.png
[20200518100656456.gif]: /images/20230312/a8dadcaa5dbe42a79f0eb19ba91cbf89.png
[20200518101132319.png]: /images/20230312/7a814612b6e34eee83790fb0b0c420eb.png