当前位置：
  1. 首页
  2. 剑指offer刷题第二期
  3. 问题详情

【链表专题】剑指 Offer 22. 链表中倒数第k个节点

本问题对应课程链接：剑指offer刷题第二期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi
469 94

共以下 94 个回答

  • lucca 普通 2022年12月30日 上午1:00 
    /**
 * 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 l, r;
        l = r = head;
        for (int i = 0; i < k; i++) {
            r = r.next;
            // 不够k个节点
            if (i < k - 1 && r == null) return null; 
        }

        while (r != null) {
            l = l.next;
            r = r.next;
        }
        return l;
    }
}
    0 赞同 0 条回复
  • 糖鑫 普通 2022年12月1日 下午8:45 
    /**
 * 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) {
        //双指针，快指针先走k步，快慢同速走，快指针到达终点，返回慢指针
        //length=N,quick=k，开始走，quick走了N-k步，结束，此时quick=N,slow=N-k，slow距离终点N-(N-k)=k
        if(head==null){return null;}//特例处理
        ListNode quick=head;
        ListNode slow=head;
        for(int i=0;i<k;i++){//快指针先走k步
            quick=quick.next;
        }
        while(quick!=null){//快慢同速走，快指针到达终点
            quick=quick.next;
            slow=slow.next;
        }
        return slow;//返回慢指针
    }
}
    0 赞同 0 条回复
  • mpweixin用户 普通 2022年11月17日 下午9:37 
    class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # 快指针比慢指针多走k步，那么当快指针遍历完，[慢指针]刚好是到倒数k的位置
        fast = pHead
        slow = pHead
        # 快指针走的时候，慢指针不走
        for i in range(0, k):
            if not fast:
                return None
            fast = fast.next # 表示指针在遍历

        # 两个指针开始同时走
        while fast:
            fast = fast.next
            slow = slow.next
        return slow
    0 赞同 0 条回复
  • 格格巫 普通 2022年11月17日 下午5:21

    下面是代码

    /**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let fast = head;
    let slow = head;
    for(let i = 0; i < k; i++){
        fast = fast.next;
    }
    while(fast){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
};
    0 赞同 0 条回复
  • PatNick 普通 2022年11月13日 上午10:25 
    def getKthFromEnd(head:ListNode,k:int)->ListNode:
    '''
    使用双指针，一个先走k步，然后两个同时走k-1步，当先走的那个走到终点时，后走的指针到达倒数第k个节点
    :param head: 头节点
    :param k: 倒是第k个节点
    :return: 头节点
    '''
    if not head:
        return head

    # 先走的指针
    first = head
    # 后走的指针
    second = head

    # first指针先走k-1步
    for _ in range(k-1):
        first = first.next

    # 双指针同时走
    while first.next:
        first = first.next
        second = second.next

    return second
    0 赞同 0 条回复
  • Mermaidᯤ⁶ᴳ 普通 2022年10月31日 下午7:10

    Definition for singly-linked list.

    class ListNode:

    def init(self, x):

    self.val = x

    self.next = None

    class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
    fast,slow=head,head
    #让快指针比慢指针多走K
    for _ in range(k):
    if not fast:return fast
    fast=fast.next
    #当快指针到NULL的时候，慢指针就是倒数第K个节点
    while fast:
    fast,slow=fast.next,slow.next
    return slow

    0 赞同 0 条回复
  • 杨帆 普通 2022年10月31日 下午5:05

    static class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode prek = head;
    ListNode cur = head;
    while(cur.next != null){
    cur = cur.next;
    k–;
    if(k <= 0){
    prek = prek.next;
    }
    }
    return prek;
    }
    }
    空间O（1）
    时间O (n)

    0 赞同 0 条回复
  • 叶页耶夜烨邺 普通 2022年10月28日 下午6:05

    快慢指针方法
    空间O（1）
    时间O (n)

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* slow = dummy;
        ListNode* fast = dummy;
        while(k--) fast = fast->next;
        while(fast != nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};
    0 赞同 0 条回复
  • 。。。。 普通 2022年10月27日 下午1:59 
    class Solution {
public:
    ListNode</em> getKthFromEnd(ListNode* head, int k) {
                if(head<span class="text-highlighted-inline" style="background-color: #fffd38;">nullptr) return head;
                ListNode* slow=head;
                ListNode* fast=head;
                for(int i =0;i<k;i++){
                    fast=fast->next;
                }
                while(fast!=NULL)
                {
                    fast=fast->next;
                    slow=slow->next;
                }
                return slow;
    }
};

    快慢指针方法
    空间O（1）
    时间O (n)

    1 赞同 0 条回复
  • 和 普通 2022年10月27日 上午8:43 
    public ListNode getKthFromEnd(ListNode head, int k) {
      //快慢双指针，让双指针同时指向头结点，之后让其中一个先走k步，之后两个指针开始一起走
        if (head == null||head.next==null) {
            return head;
        }
        ListNode list=head;
        ListNode third=head;
        for (int i = 0; i < k; i++) {
            if (list==null){
                return list;
            }else{list=list.next;}
        }
        while (list!=null){
            list=list.next;
            third=third.next;
        }
        return third;
    }
    0 赞同 0 条回复
  • hmmm 普通 2022年10月26日 下午9:44

    代码如下：

    “`c++“`
    /**
    * Definition for singly-linked list.
    * struct ListNode {
    * int val;
    * ListNode *next;
    * ListNode(int x) : val(x), next(NULL) {}
    * };
    */
    class Solution {
    public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
    if(head == NULL)
    return NULL;
    ListNode *p = head;
    ListNode *q = head;
    while(k– && p!=NULL)
    {
    p = p->next;
    }
    while(p)
    {
    p = p->next;
    q = q->next;
    }
    return q;

    }

    };
    时间复杂度：O(n)
    空间复杂度：O(1)

    0 赞同 0 条回复
  • 彭靖 永久会员 2022年10月26日 下午3:52 
    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) 
    {
        ListNode* p1;
        ListNode* p2;
        p1=head;
        p2=head;
        for(int i=0;i<k-1;i++)
        {
            p2=p2->next;
        }
        while(p2->next!=NULL)
        {
            p1=p1->next;
            p2=p2->next;
        }

        return p1;

    }
};

    新手打卡

    0 赞同 0 条回复
  • XR 普通 2022年10月26日 上午9:36

    /思路
    *先得到链表的结点总数，再利用循环遍历到倒数第K个结点    /

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode <em>next;
 * };
 */
//获取链表结点总数
int getLength(struct ListNode</em> head){
    int length = 0;
    while(head){
        head = head->next;
        ++length;
    }
    return length;
}

struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    int length = 0;
    struct ListNode * temp = malloc(sizeof(struct ListNode));
    temp->val = 0; temp->next = head;
    length = getLength(head);
    struct ListNode* cur = temp;
    for(int i = 0; i < length - k + 1; i++){
        cur = cur->next;
    }
    //cur->next = cur->next->next;
    struct ListNode* ans = cur;
    free(temp);
    return ans;
}
    0 赞同 0 条回复
  • Xiao 普通 2022年10月25日 下午9:04 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode p=head;
        ListNode n=p;
        for(int i=0;i<k;i++){//让快指针先走
            n=n.next;
        }
        while(n!=null){
            p=p.next;
            n=n.next;
        }
        return p;

    }
}
    0 赞同 0 条回复
  • 努力刷题 普通 2022年10月25日 上午6:40 
    class Solution(object):
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        fast = slow = head
        i = 0
        while fast:
            if i >= k:
                slow = slow.next
            fast = fast.next
            i += 1
        return slow
时间复杂度 O(n)
空间复杂度 O(1)
    0 赞同 0 条回复
  • 小趴菜 永久会员 2022年10月25日 上午12:26

    java
    快慢指针，一个移动k另一个再移动
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode fastNode=head;
    ListNode slowNode=head;
    for(int i = 0;i<k;i++){
    fastNode=fastNode.next;
    }
    while(fastNode!=null){
    fastNode=fastNode.next;
    slowNode=slowNode.next;
    }
    return slowNode;

    }

    }

    0 赞同 0 条回复
  • 云 永久会员 2022年10月24日 下午7:53 
    import java.util.*;
解法1：
这个题用了 len-k的想法 就可以把后面的数据输出，但是要用到len,所以：
（1）第一步求长度
（2）长度-K 就可以得到倒数k的数据啦

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可


     * @param pHead ListNode类
 * @param k int整型
 * @return ListNode类
 */
public ListNode FindKthToTail (ListNode pHead, int k) {
    // write code
    ListNode p1 = pHead;
    int len = 0;
    for (; pHead != null; pHead = pHead.next) {
        len++;
    }
    if (len < k) {
        return null;
    }
    for (int i = 0; i < len - k; i++) {
        p1 = p1.next;

    }
    return p1;


}

    

    }
    

    解法2：
    
   试一下双指针的方式  定义一个fast快指针和一个slow慢指针，
    
     fast+K，slow还是原来位置，然后同时移动，直到fast指的是null，
    

    import java.util.*;
    

    /*
    
 * public class ListNode {
    
 *   int val;
    
 *   ListNode next = null;
    
 *   public ListNode(int val) {
    
 *     this.val = val;
    
 *   }
    
 * }
    
 */
    

    public class Solution {
    
    /**
    
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    

         *
    
     *
    
     * @param pHead ListNode类
    
     * @param k int整型
    
     * @return ListNode类
    
     */
    
    public ListNode FindKthToTail (ListNode pHead, int k) {
    
        // write code here
    
        ListNode fast=pHead;
    
        ListNode slow=pHead;
    
        for(int i=0;i
    0 赞同 0 条回复
  • 🚲南下 普通 2022年10月24日 上午9:46

    复杂度：
    时间复杂度为O(n)，空间复杂度为O(1)

    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* fast = head; //定义快慢指针
        ListNode* slow = head;
        for(int i = 0; i < k; i++){ //快指针先走k步
            if(fast == nullptr){ 
                return nullptr;
            }
            fast = fast->next; 
        }
        while(fast != nullptr){ //快指针走k步后，两个指针一起走
        //直到快指针遍历完链表
            fast = fast->next;
            slow = slow->next;
        }
        return slow; 

    }
};
    0 赞同 0 条回复
  • 啊哈 普通 2022年10月24日 上午12:05 
    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {

        //定义指针
        ListNode* cur = head;
        ListNode* fast= head;
        //快指针走k个节点
        while(fast != NULL && k>0){
            fast = fast -> next;
            k--;
        }
        // fast不为NULL，快慢同时移动
        while(fast != NULL){
            cur = cur -> next;
            fast = fast -> next;
        }
        return cur;
    }
};

    时间复杂度O(n)
    空间复杂度O(1)

    0 赞同 0 条回复
  • 阿白 普通 2022年10月23日 下午10:43

    1、两个指针，慢的指向头，快的指向第k个结点（如果有）。接下来快慢同步++，直到快的为nullptr停止，此时慢的刚好指向了倒数第k个节点。
    2、时间复杂度O（n），空间复杂度O（1）

    class ListNode{
public:
    ListNode(){ val = 0; next = nullptr; }
    ListNode(int m) :val(m){};
    ListNode *delListNode(ListNode *head, int K);
private:
    int val;
    ListNode *next;
};

ListNode *ListNode::delListNode(ListNode *head, int K)
{
    if (head == nullptr)
        return head;
    ListNode *fast=head;
    ListNode *slowK=head;
    for (int i = 0; i < K; ++i)
    {
        if (fast != nullptr)
            fast = fast->next;
        else
            return nullptr;

    }
    while (fast != nullptr)
    {
        fast = fast->next;
        slowK = slowK->next;
    }
    return slowK;
}
    0 赞同 0 条回复
  • Stoician 普通 2022年10月23日 下午8:34

    打卡C++
    class Solution {
    public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
    ListNode* cur = head;

        int cnt = 1;
    while(cur->next != NULL){
        cur = cur->next;
        cnt++;
    }
    if(k <= cnt){
        int flag = cnt - k;
        while(flag){
            head = head->next;
            flag--;
        }
    }


    return head;

}

    };

    0 赞同 0 条回复
  • cxc 普通 2022年10月23日 下午8:16 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //快慢指针
        ListNode fast = head;
        ListNode slow = head;
        int i = 0;
        while(fast != null) {
            if(i >= k) {
                slow = slow.next;
            }

            fast = fast.next;
            i++;
        }

        return slow;
    }
}
    0 赞同 0 条回复
  • Ruby🗽 普通 2022年10月23日 下午5:25 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode pre = head;
        ListNode temp = head;
        int i = 0;
        while (temp != null) {
            if (i >= k){
                pre = pre.next;
            }
            temp = temp .next;
            i++;
        }
        return pre;
    }
}

    时间复杂度 n
    空间复杂度 1

    0 赞同 0 条回复
  • Gg 普通 2022年10月23日 下午4:39 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        // 定义快慢指针
        ListNode fast = head;
        ListNode slow = head;
        int i = 0;
        // 遍历链表
        while(fast != null){
            // 快指针走了k位后，开始移动慢指针。快指针为空，慢指针走了n-k
            if(i >= k){
                slow = slow.next;
            }
            fast = fast.next;
            i++;
        }
        return slow;
    }
}
    0 赞同 0 条回复
  • just 普通 2022年10月23日 下午4:21

    //c++实现
    class Solution {
    public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
    ListNode* dummy=new ListNode(0,head);
    ListNode* l=dummy;
    ListNode* r=dummy;
    while(k–) r=r->next;
    while(r->next){
    r=r->next;
    l=l->next;
    }
    return l->next;

    }

    };

    0 赞同 0 条回复
  • symbol 普通 2022年10月23日 下午12:24 
    func getKthFromEnd(head *ListNode, k int) *ListNode {
    // 先计算出链表长度length 然后 返回第length-k+1个
    length := 0
    for temp := head;temp != nil;temp = temp.Next{
        length ++
    }
    //返回第length -k +1个
    tem := head
    for i := 1;i < length - k +1;i++{
        tem = tem.Next
    }
    return tem
}

    时间复杂度：O(n)，其中 n=length为链表的长度。需要两次遍历。
    空间复杂度：O(1)。

    0 赞同 0 条回复
  • 云雾里 普通 2022年10月23日 上午11:35 
    /**
 * 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) {
//你好
        if(head==null){
            return head;
        }
        ListNode now = head;
        ListNode target=null;
        while(now!=null){
            if(k==1){
                target=head;
            }
            now=now.next;
            k--;
            if(k<1&&now!=null){
                target=target.next;
            }
        }
        return target;
    }
}
    0 赞同 0 条回复
  • 浅夏的无奈 普通 2022年10月23日 上午8:15 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //创建快慢指针
        ListNode pre=head,cur=head;
        //pre向前跑k个节点
        for(int i=0;i<k;i++){
            pre=pre.next;
        }
        //两个节点一起跑
        while(pre!=null){
            pre=pre.next;
            cur=cur.next;
        }
        //返回结果
        return cur;
    }
}
    0 赞同 0 条回复
  • mpweixin用户 永久会员 2022年10月22日 下午11:31 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode pre=head;
        for(int i=1;i<k;i++){
            pre = pre.next;
        }
        ListNode after=head;
        while(pre.next!=null){
             pre=pre.next;
             after=after.next;
        }
        return after;

    }
}
    0 赞同 0 条回复
  • 优秀市民 普通 2022年10月22日 下午10:48 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode former = head,latter=head;
        for(int i = 0; i<k; i++){
            former = former.next;
        }
        while(former != null){
            former = former.next;
            latter = latter.next;
        }
        return latter;


    }
}

    时间复杂度o(N)
    空间复杂度o(1)

    0 赞同 0 条回复
  • -辰华- 永久会员 2022年10月22日 下午10:39

    解法一：使用快慢指针

    /**
 * 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) {
        if (head == null || k == 0) return null;
        // 初始化快慢指针
        ListNode fast = head;
        ListNode slow = head;
        // 先让fast走k步
        while (k-- > 0 && fast != null) {
            fast = fast.next;
        }
        // 然后，fast和slow一起走，直到fast指向null时停止，此时slow的位置为倒数第k个节点
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

    解法二：求链表长度n，走（n-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) {
        // 先求链表长度n
        ListNode node = head;
        int n = 0;        
        while (node != null ) {
            node = node.next;
            n++;
        }
        node = head;
        // 然后，node走（n-k）步，此时，node所在位置为倒数第k个节点
        while (n-- > k && node != null) {
           node = node.next;
        }
        return node;
    }
}

    时间复杂度均为：O(n)
    空间复杂度均为：O(1)

    0 赞同 0 条回复
  • Tolkien 永久会员 2022年10月22日 下午10:35

    双指针
    1. 时间复杂度：O(n)
    2. 空间复杂度：O(1)
    3. 代码

    public ListNode getKthFromEnd1 (ListNode head, int k) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        // 1. 设置两个指针
        ListNode A = dummyHead;
        ListNode B = dummyHead;

        // 2. 移动其中一个指针k个节点
        for (int i = 0; i < k; i++) {
            if (A == null) {
                return null;
            }
            A = A.next;
        }

        // 3. 同时移动两个节点，直到先移动的指针遍历完成
        while (A != null) {
            A = A.next;
            B = B.next;
        }

        return B;
    }
    0 赞同 0 条回复
  • 波波_1936 普通 2022年10月22日 下午9:14 
        public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null || k <= 0) return head;
        /**
         * 利用快慢指针 快指针和慢指针差就是k
         */
        ListNode fast = head;
        ListNode slow = head;

        while (true) {
            if (k > 0) {
                fast = fast.next;
                k--;
            } else {
                fast = fast.next;
                slow = slow.next;

            }
            if (fast == null) {
                break;
            }

        }

        return slow;

    }

    时间复杂度O(n)
    空间复杂度O(1)

    0 赞同 0 条回复
  • 晨 普通 2022年10月22日 下午8:41 
    class Solution(object):
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        #头指针判空
        if not head:
            return null;
        #快、慢指针初始化
        quick, slow = head, head
        #快指针先走k步
        while k > 0:
            quick = quick.next
            k -= 1
        #两指针 一起走，直至快指针走到末尾，输出慢指针
        while quick:
            quick = quick.next
            slow = slow.next
        return slow
    0 赞同 0 条回复
  • Monster Dump 普通 2022年10月22日 下午8:18
    • 代码实现 (Java)
        public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null) {
            return head;
        }
        ListNode curr = head;
        ListNode kNode = head;
        int i = 0;
        while (curr != null && i < k) {
            curr = curr.next;
            i++;
        }
        while (curr != null) {
            kNode = kNode.next;
            curr = curr.next;
        }
        return kNode;
    }
    • 时间复杂度: O(n)
    • 空间复杂度: O(1)
    0 赞同 0 条回复
  • Magi 普通 2022年10月22日 下午7:34

    “`java
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
    //首先判断特殊情况,只有一个头节点
    if (head == null) {
    return head;
    }

        //使用双指针操作会方便很多，现在进行相关的定义
    //本题从1开始计数，即链表的尾节点是倒数第1个节点。
    ListNode fast = head;
    ListNode slow = head;

    //先让快指针先走k步
    for (int i = 0; i < k; i++) {
        //先判断快指针为空的情况
        if (fast == null) {
            return null;
        }
        fast = fast.next;
    }

    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}
    0 赞同 0 条回复
  • yanshuojune 普通 2022年10月22日 下午7:17 
    class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        # 解体方法：快慢指针
        fast ,slow = head, head
        #先将快指针移动到第k+1个节点
        while fast and k > 0:
            fast = fast.next
            k -= 1
        #同时移动快慢指针到各自的下一节点，指导快指针指向尾节点，此时的慢指针指向倒数第k个节点
        while fast:
            fast = fast.next
            slow = slow.next
        return slow

    时间复杂度：O(n)
    空间复杂度：O(1)
    方法二：使用数学的方法，通过遍历链表得到链表长度n，从前往后遍历，第n-k个节点即为倒数第k个节点，具有相同时间和空间复杂度

    0 赞同 0 条回复
  • 韩杰 普通 2022年10月22日 下午7:15

    1,通过地哥给的提示，一个快指针，一个慢指针。快指针先走k，之后同步走。
    2，时间复杂度O（n），空间复杂度不清楚。

    /**
 * 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) {
        if(head ==null){
            return null;
        }

        ListNode quick = head;
        ListNode slow =head;

        for(int i = 0 ;i < k ;i++){
            if(quick==null){
                return null;
            }
            quick = quick.next;
        }
        while(quick!=null){
            quick = quick.next;
            slow = slow.next;
        }
        head =slow;
        return head;
    }
}
    0 赞同 0 条回复
  • cxxz 普通 2022年10月22日 下午6:52

    结合题目提示，可以采用两个指针，先让快指针与慢指针的间隔为k-1（倒数第几个是从1开始查），然后快慢指针同时走，当快指针访问到null 时，慢指针即是倒数第k个指针，巧妙。

    ListNode* FindKthToTail(ListNode* pHead, int k) {
        if (pHead == nullptr || k == 0)
            return nullptr;

        ListNode* slow, *fast;
        slow = fast = pHead;
        for (int i = 0; i < k-1; i++)
        {
            if (fast->next == nullptr)
                return nullptr;
            fast = fast->next;
        }

        while ( fast->next != nullptr )
        {
            fast = fast->next;
            slow = slow->next;
        }

        return slow;
    }

    时间复杂度 O(n)
    空间复杂度 O(1)

    0 赞同 0 条回复
  • 刺猬 普通 2022年10月22日 下午6:47 
    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* pre = head;
        ListNode* cur = head;
        int i=1;
        while(cur->next != nullptr)
        {
            if(i < k)
            {
                cur = cur->next;
                i++;
            }
            else
            {
                pre = pre->next;
                cur = cur->next;
            }
        }
        return pre;
    }
};

    时间复杂度O(N)
    空间复杂度O(1)

    0 赞同 0 条回复
  • 泡芙 永久会员 2022年10月22日 下午6:45

    解法：快慢指针
    思路：fast 比 slow 多走 k 步，然后 slow 和 fast 一起走，当 fast = null 时，slow 正好是倒数第 k 个节点

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null) {
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;

        // fast 先走 k 步
        for(int i = 0; i < k; i ++) {
            fast = fast.next;
        }

        // fast 和 slow 一起走
        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

    时间复杂度：O(n)
    空间复杂度：O(1)

    0 赞同 0 条回复
  • YZ 普通 2022年10月22日 下午6:35 
    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
    //双指针解法
    ListNode *fast = head;  //设置一个fast指针
    ListNode *slow = head;  //设置一个slow指针
    if(head == NULL)    //判断链表是否为空
    {
        return NULL;
    }
    for(int i = 0;inext;
    }
    while(fast!=NULL)  //然后快慢指针同步走，直至fast到达NULL，slow到达倒数第K个结点
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;  //返回slow便是倒数第k个节点
    }
};

    刚接触到快慢指针，一开始不会使用，使用的是先求出链表长度，再用链表长度减去k，得到倒数第k个结点在正数第几个位置，然后通过for循环达到
    快慢指针的解题思路
    1.关系：链表空指针(NULL)和倒数第k个结点差距为k个距离
    2.可以设置fast指针和slow指针
    3.先让fast指针先走k步，再让fast和slow同步进行
    4.等fast达到NULL时，slow就是倒数第k个结点
    时间复杂度O(n)
    空间复杂度O(1)

    0 赞同 0 条回复
  • 绍熙 普通 2022年10月22日 下午6:33

    思路：快慢指针，考虑越界等问题

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null || k < 1) return null;

        // 快指针
        ListNode h = head;
        // 指针
        ListNode t = head;
        // 两指针的距离
        int dis = 0;

        while(h.next != null){
            if(dis < (k-1)){
                dis++;
            }else{
                t = t.next;
            }
            h = h.next;
        }
        return dis < (k-1)? null: t;
    }
}
    0 赞同 0 条回复
  • 酥合 普通 2022年10月22日 下午5:20 
    /**
 * 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) {
        int count = 0;
        ListNode p = head;
        while(p != null) {
            count++;
            p = p.next; 
        }
        if(k > count) {
            return null;
        }
        p = head;
        while(count - k > 0) {
            p = p.next;
            count--;
        }
        return p;
    }
}

    时间复杂度: O(n)
    空间复杂度: O(1)

    0 赞同 0 条回复
  • cute. 普通 2022年10月22日 下午4:24

    思路: 快慢指针
    a.初始化快慢指针
    b.fast向后移动k个位置，然后fast和slow再一起向后移动；
    c.当fast走到最后的时候，slow的位置就是倒数第k个位置

    var getKthFromEnd = function(head, k) {
if(head == null)
{
        return null;
      }
let fast = head;
let slow = head;
let index = k - 1;
while(index-- !== 0 && fast.next !==null)
fast = fast.next;
while(fast.next !== null && slow.next !== null) {
fast = fast.next;
slow = slow.next;
}
    return slow;
};

    ● 时间复杂度: O(n)
    ● 空间复杂度: O(1)

    0 赞同 0 条回复
  • Y7n05h 普通 2022年10月22日 下午4:07 
    class Solution {
public:
    ListNode *getKthFromEnd(ListNode *head, int k) {
        ListNode t(0);
        t.next = head;
        auto *fast = &t;
        auto *slow = &t;
        for (int i = 0; i < k; ++i) {
            fast = fast->next;
        }
        while (fast->next) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow->next;
    }
}

    时间复杂度：O(n)
    空间复杂度：O(1)

    0 赞同 0 条回复
  • 你有点可爱喔 普通 2022年10月22日 下午3:41

    顺序查找，算出长度。然后找到k的位置就是长度size-k的值
    空间复杂度O(1)
    时间复杂度O(n);

        public ListNode getKthFromEnd(ListNode head, int k) {
        //得到长度
        //倒数k的位置就是长度-k
        int size = 0;
        ListNode temp = null;
        // 获取长度
       for(temp = head;temp!=null;temp=temp.next){
           size++;
       }
        int lastindex = size-k;
        //移动节点找到k的
        for(temp = head;size>k;size--){
            temp = temp.next;
        }
        return temp;

    }
    0 赞同 0 条回复
  • 晨渊 普通 2022年10月22日 下午3:21 
    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        //双指针
        if(head == NULL || k<1)
            return head;
        ListNode *fast=head, *slow=head;//定义快指针和慢指针,快指针先走k个节点

        for(int i=1;i<k;i++){  //fast从k位置开始
            fast = fast->next;
        }

        while(fast->next!=NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

    //时间复杂度 O(n)
    //空间复杂度O(1)

    0 赞同 0 条回复
  • 追 普通 2022年10月22日 下午2:16 
    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *former = head, *latter = head;
        for(int i = 0; i < k; i++) former = former->next;
        while(former != nullptr){
            former = former->next;
            latter = latter->next;
        }
        return latter;
    }
};

    指针指向链表结尾：p nullptr;

    0 赞同 0 条回复
  • 小肸 永久会员 2022年10月22日 下午1:41

    三种思路：
    思路一：把链表翻转，从链表头节点走k步，并将前面k个节点再翻转。时间复杂度O(N)，空间复杂度O(1)。
    思路二：先遍历链表，得到链表长度len，从头节点走len – k步。时间复杂度O(N)，空间复杂度O(1)。
    思路三: 快慢指针，快指针先走k步，随后慢指针和快指针一起走，当快指针遍历完链表后，慢指针正好走到倒数第k个节点。时间复杂度O(N)，空间复杂度O(1)。

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        while (k -- > 0) {
            if (fast == null) {
                System.exit(1);
            }
            fast = fast.next;
        }
        ListNode slow = head;
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
    0 赞同 0 条回复
  • 虾仁猪心 普通 2022年10月22日 下午12:00

    思路：
    本题适合使用快慢指针，让快指针fast先走k步，然后快慢指针一起循环链表，当快指针fast走到链表尾部的时候（fast指针走到null时），慢指针所在位置就为链表中倒数第k个节点了。
    时间复杂度 O（n）
    空间复杂度 O（1）

    public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        ListNode fast = pHead;
        ListNode slow = pHead;
        for(int i=0;i<k;i++){
            if(fast==null){
                return slow = null;
            }
            fast = fast.next;
        }
        while(fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
    0 赞同 0 条回复
  • 潜行1 我是火车王！ 普通 2022年10月22日 上午11:50 
    func getKthFromEnd(head *ListNode, k int) *ListNode {
    if head == nil {
        return head
    }

    slow, fast := head, head

    for i := 0; i < k; i++ {
        // 链表的长度没有k
        if fast == nil {
            return nil
        }
        fast = fast.Next
    }

    for fast != nil {
        slow = slow.Next
        fast = fast.Next
    }

    return slow
}
    0 赞同 0 条回复
  • mpweixin用户 普通 2022年10月22日 上午11:35 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;

        //先让快指针先走k步,当快指针走到空的时候，返回慢指针
        for(int i=0;i<k;i++){
             if(fast!=null){
                 fast=fast.next;
             }
        }

        //同时开时走
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }

        //返回慢指针

        return slow;
    }
}
    0 赞同 0 条回复
  • wxc 普通 2022年10月22日 上午10:56

    额

    class Solution(object):
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        l = 0
        x = head
        while(x):
            l += 1
            x = x.next
        for i in range(l-k):
            head = head.next
        return head
    0 赞同 0 条回复
  • 派大星 普通 2022年10月22日 上午10:30 
    //使用快慢指针遍历，快指针在慢指针前k-1个位置，快指针到达链表尾部，慢指针位于倒数第k个节点
//时间复杂度O(n)
//空间复杂度O(1)
public class Solution {
    public ListNode listFromEnd(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode slowNode = head;
        ListNode fastNode = head;
        for (int i = 0; i < (val - 1); i++) {
            fastNode = fastNode.next;
        }
        while (fastNode.next != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next;
        }
        return slowNode;
    }
}
    0 赞同 0 条回复
  • mpweixin用户 普通 2022年10月22日 上午10:17

    快慢指针，一次遍历

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode q = head;
        ListNode p = head;
        for(int i = 0; i < k; i++){
            q = q.next;
        }
        while(q != null){
            q = q.next;
            p = p.next;
        }
        return p;
    }
}
    0 赞同 0 条回复
  • 是梦终空 永久会员 2022年10月22日 上午9:24

    先遍历求出该链表有多少个节点，
    然后-去k，
    得到他从哪个节点开始
    再定义一个新头结点（这里好像感觉不用，直接用head就行），i=1开始，遍历到count-k,返回新的头结点
    时间复杂度:O(n)
    空间复杂度:O(1）

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head.next == null)   return head;
        int count = 1;
        ListNode list = head;
        while(list.next!=null){
            list = list.next;
            count++;
        }
        ListNode li = head;
        for(int i = 1;i<=count-k;i++){
            li = li.next;
        }
        return li;
    }
}
    0 赞同 0 条回复
  • 单个酒窝儿 普通 2022年10月22日 上午9:12

    用双指针来做
    1、先定义两个指针 pre cur 同时指向头节点
    2、用一个for循环让cur指针先走k步
    3、while循环，当cur NULL时，pre指针所指向的就是倒数第k个节点，将pre返回就可以
    时间复杂度O(n) 空间复杂度O(1)

    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if(head == NULL) return NULL;

        ListNode* pre = head;
        ListNode* cur = head;
        for(int i=0; i<k ;i++){
            cur = cur->next;
        }

        while(cur!=NULL){
            pre = pre->next;
            cur = cur->next;
        }
        return pre;
    }
};
    0 赞同 0 条回复
  • 乱世枭雄 普通 2022年10月22日 上午8:51

    用双指针来做，前后指针相差k，当后指针指向末尾，前指针正好指向倒数第k个节点，返回即可

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode p;
        ListNode q;
        int i;
        p=head;q=p;
        for(i=0;i<k;i++){
            q=q.next;
        }
        while(q!=null){
            p=p.next;
            q=q.next;
        }
        return p;
    }
}
    0 赞同 0 条回复
  • 糖香香 普通 2022年10月22日 上午1:55 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //看了题解，也可以使用双指针
        int n=0;
        ListNode node = null;

        //遍历获得链表长度
        for( node = head; node != null; node = node.next){
            n++;
        }
        //获得输出头节点的位置
        for( node = head; n > k ; n--){
            node =node.next;
        }
        return node;
    }
}
    0 赞同 0 条回复
  • 黎昕 普通 2022年10月22日 上午1:31

    双指针/快慢指针

    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* p1=head;
        ListNode* p2=head;
        for(int i=0;i<k;i++)
        {
            p2=p2->next;
        }
        while(p2!=NULL)
        {
            p1=p1->next;
            p2=p2->next;
        }
        return p1;


<pre><code>}
</code></pre>

};
    0 赞同 0 条回复
  • 星河 普通 2022年10月22日 上午1:03 
    //方法一
//快指针先走k步，然后快慢指针一起走
//当快指针到达链表尾时，慢指针到最后k个位置
//时间O(N)，空间O(1)
//方法二，按照第52题的思想
//第一遍遍历，求整个链表的长度n
//第二遍遍历，指针走n-k步，即倒数第k个位置
//时间O(N)，空间O(1)
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head, slow = head;
        while(k > 0){
            fast = fast.next;
            k--;
        }
        while(fast != null){
           slow = slow.next;
        fast = fast.next;
}
   return slow;
    }
}
    0 赞同 0 条回复
  • lone。 普通 2022年10月22日 上午12:59 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {

        if (head == null || k < 1) {
            return null;
        }

        int step = 1;

        //快指针，先向下遍历移动
        ListNode quick = head;
        //慢指针，待快指针移动至正向第K个节点，再向下遍历移动
        ListNode slow = head;
        //当快指针移动到最后结束，慢指针即是倒数第k个节点
        while (quick.next != null) {
            if (step >= k) {
                slow = slow.next;
            } else {
                step++;
            }
            quick = quick.next;
        }

        return step >= k ? slow : null;
    }
}

    时间复杂度：O(N)

    空间复杂度：O(1)

    0 赞同 0 条回复
  • 溴麝香草酚蓝 普通 2022年10月22日 上午12:59
    • 思路
      1. 使用单指针需要遍历两次，一次获取节点数，一次获取倒数第k个节点；使用双指针则可以只遍历一次。
      2. 快慢双指针可以通过控制两个指针之间的距离来保证在快指针到达链表尾时，慢指针正好指向倒数第k个节点或头节点。
      3. 注意头节点为null直接返回null；当快指针遍历完链表但与慢指针的距离(dis)仍然小于k时，视头节点(head)为倒数第k个节点。

    • 代码

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

    • 时间复杂度：O(n)

    • 空间复杂度：O(1)

    0 赞同 0 条回复
  • 訁訁訁訁訁 普通 2022年10月22日 上午12:26

    时间复杂度O(n)空间复杂度O(1)

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null) return null;
        ListNode fast = head;//快指针
        ListNode slow = head;//慢指针
        while(k-- > 0){
            if(fast == null){
                return null;
            }
            fast = fast.next;//快指针先走k步
        }
        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

    ###

    0 赞同 0 条回复
  • Error 普通 2022年10月22日 上午12:21 
    class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        pre, cur = head, head
        for _ in range(k):
            cur = cur.next

        while cur:
            pre = pre.next
            cur = cur.next
        return pre

    时间复杂度 O(n)

    0 赞同 0 条回复
  • Spermalow 普通 2022年10月21日 下午11:43 
    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode * currentNode = head;
        // 记录往后走K步的指针
        ListNode * nextKNode = head;
        // 让nextKNode往后走k步
        while (k --) {
            nextKNode = nextKNode->next;
        }
        // 让两个指针同时走，当先走K步的nextKNode指针走到尾后，currentNode即为指向倒数第k个结点位置
        while (nextKNode) {
            nextKNode = nextKNode->next;
            currentNode = currentNode->next;
        }
        return currentNode;
    }
};

    时间O(n), 空间O(1)

    0 赞同 0 条回复
  • Chin 普通 2022年10月21日 下午11:34 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null) return head;

        ListNode front = head;
        ListNode behind = head;
        for(int i=0;i<k;i++){
            front = front.next;
        }

        while(front != null){
            front = front.next;
            behind = behind.next;
        }
        return behind;
    }
}

    快慢指针，快指针先走k步，快慢指针再一起走，当快指针走到头的时候，此时慢指针指向的节点就是倒数第k个
    时间复杂度O(n) — 只需遍历一次
    空间复杂度O(1)

    0 赞同 0 条回复
  • 庄重 普通 2022年10月21日 下午10:58 
    //还有个思路，是先反转链表，然后直接找正数k的位置( 即为原链表的倒数k )，
//但是有些不符合题意，他还要返回原链表目标结点的后续节点。这就需要保存原来链表的顺序，有些麻烦
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        //快慢指针的思路
        ListNode* pFast = head;//快指针遍历，慢指针即为要找节点
        ListNode* pSlow = head;

        for(int i = 0; inext;
        }

        for(; pFast ;){
            pFast = pFast->next;
            pSlow = pSlow->next;
        }

        return pSlow;
    }
};
//时间复杂度O(n)
//空间复杂度O(1)
    0 赞同 0 条回复
  • 易水寒 永久会员 2022年10月21日 下午10:55 
    class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(p1 != null && p2 != null) {
            if(p1.val <= p2.val) {
                cur.next = p1;
                p1 = p1.next;
            }
            else {
                cur.next = p2;
                p2 = p2.next;
            }
            cur = cur.next;
        }
        if(p1 != null) {
            cur.next = p1;
        }
        else {
            cur.next = p2;
        }
        return dummy.next;
    }
}
//复杂度O(n)
    0 赞同 0 条回复
  • 马啸天 永久会员 2022年10月21日 下午10:49 
    public class Solution {
    public ListNode getKthFromEnd(ListNode head , int k) {
        //1.按照帅地的思路解题：设置快慢指针，两个相差k
        if (k < 0)
            throw new IllegalArgumentException("get failed,cause k is illegal.");
        if (head == null)
            return null;
        ListNode pre = head;
        ListNode cur = head;
        for (int i = 0; i < k; i++) {
            cur = cur.next;
        }
        while (cur != null) {
            cur = cur.next;
            pre = pre.next;
        }
        return pre;
    }
}

class Solution2 {
    public ListNode getKthFromEnd(ListNode head , int k) {
        //题目的关键在于找到第k个元素，因此可以简单循环遍历一下
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode prev = dummyHead;
        //计算出一共有多少元素
        int count = 0;
        while (prev.next != null) {
            count++;
            prev = prev.next;
        }

        ListNode ret = dummyHead;
        //倒数第k个，就是正数第count-k+1个
        for (int i = 0; i < count - k + 1; i++) {
            ret = ret.next;
        }
        return ret;
    }
}
    0 赞同 0 条回复
  • mpweixin用户 普通 2022年10月21日 下午10:41 
    /**
 * 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 fast = head;       // 快指针
        ListNode slow = head;       // 慢指针
        for(int i=0;i<k;i++)        // 快指针先走k步
            fast = fast.next;
        while(fast!=null){          // 快慢指针同时走，直到快指针走到头
            fast = fast.next;
            slow = slow.next;
        }
        return slow;                // 返回慢指针，即为倒数第k个节点
    }
}

// 时间复杂度: O(n)
// 空间复杂度: O(1)
    0 赞同 0 条回复
  • Asphyxia 普通 2022年10月21日 下午10:23

    双指针

    /**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        ListNode* low = pHead;
        ListNode* fast = pHead;
        int i=0;
        while(fast){
            if(i>=k){
                low = low->next;
            }
            fast = fast->next;
            i++;
        }
        if(i<k){
            return NULL;
        }
        return low;
    }
};
    0 赞同 0 条回复
  • 秊 永久会员 2022年10月21日 下午10:13

    注意看题

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null) return null;

        ListNode pre = head;
        ListNode cur = head;
        for (int i = 0; i < k; ++i) {
            cur = cur.next;
        }
        while (cur != null) {
            pre = pre.next;
            cur = cur.next;
        }

        return pre;
    }
}
    0 赞同 0 条回复
  • Haoyun 普通 2022年10月21日 下午9:59

    用虚拟头结点,遍历到第 链表长度-k 个节点返回

    var getKthFromEnd = function(head, k) {
   let dummy = new ListNode(0);
   dummy.next = head;
   let length = 0;
   while(head) {
      length ++;
      head = head.next;
   }
   let n = length - k;
   while(n--) {
     dummy = dummy.next;
   }

   return dummy.next;
};
    0 赞同 0 条回复
  • MR.SandMan 普通 2022年10月21日 下午9:39 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode pre = head;
        ListNode cur = head;
        for (int i = 0; i < k - 1; i++) {
            cur = cur.next;
        }
        while(cur.next != null) {
            cur = cur.next;
            pre = pre.next;
        }
        return pre;
    }
}

    先后两个节点，快速节点先走k步，然后两个节点一起走，知道快速节点到头，慢速节点就是倒数第k个节点

    0 赞同 0 条回复
  • T 普通 2022年10月21日 下午9:21

    下面是代码

    /**
 * 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) {
        //检查空指针
        if(head == null) return head;
        ListNode fast = head;
        ListNode slow = head;
        //快指针先走
        while(k > 0 && fast != null) {
            fast = fast.next;
            k--;
        }
        //慢指针到达指定地点
        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
    0 赞同 0 条回复
  • xye 普通 2022年10月21日 下午9:03 
    func getKthFromEnd(head *ListNode, k int) *ListNode {
    n := 0
    for node := head; node != nil; node = node.Next{
        n++
    }
    kth := head
    for kth = head; n > k; n--{
        head = head.Next
        kth = head
    }

    return kth
}

    先计算出链表长度，再n-k找到相应节点

    0 赞同 0 条回复
  • @ 普通 2022年10月21日 下午9:03

    差点看成删除链表中的倒数第K个节点了

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode slow = head;
        ListNode fast = head;

        for (int i = 1; i < k; i++) {
            fast = fast.next;
        }

        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }


        return slow;

    }
}
    0 赞同 0 条回复
  • So 普通 2022年10月21日 下午9:02

    第一天第二题

    /**
 * 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) {
        if (k <= 0 || head == null) {
            return null;
        }
        ListNode pTemp = head, pK = null;
        for (int count = 1; count < k; count++) {
            if (pTemp != null) {
                pTemp = pTemp.next;
            }
        }
        while (pTemp != null) {
            if (pK == null) {
                pK = head;
            } else {
                pK = pK.next;
            }
            pTemp = pTemp.next;
        }
        if (pK != null) {
            return pK;
        }
        return null;
    }
}
    0 赞同 0 条回复
  • 如梦似歌 普通 2022年10月21日 下午8:58

    //先定义两个指针p,r指向头结点，第一次遍历r获得链表的长度，第二次遍历p到链表的r-k+1位置处。
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
    int len = 1; //len记录链表的长度
    ListNode p = head;
    ListNode r = p;
    while(r.next != null){
    len++;
    r = r.next;
    }
    //len表示链表的总长度，则需要删除的节点在链表中的位置为len-k+1
    for(int i=1; i<=len-k; i++){
    p = p.next; //使p指针指向被删除的节点
    }
    head = p;
    return head;
    }
    }

    0 赞同 0 条回复
  • 狗蛋儿 普通 2022年10月21日 下午8:42

    这里使用的是快慢指针的方法，快与慢的就是倒数数字

    细节：虚拟节点的快慢节拍以及最后返回指针的指向

    class Solution {
  public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        if (pHead == nullptr) return nullptr;
        ListNode* fast = new ListNode(0);
        fast->next = pHead;
        ListNode* slow = fast;
        while (k-- && fast != nullptr) {
            fast = fast->next;
        }
        if(fast == nullptr) return nullptr;
        fast = fast->next;
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        slow = slow->next;
        delete fast;
        return slow;
    }
};
    0 赞同 0 条回复
  • 194分贝 普通 2022年10月21日 下午8:40 
    class Solution {
  public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        ListNode* p = pHead, *q = pHead; // 双指针法
        while (k--) {
            if (p) p = p->next;
            else return nullptr;
        }
        while (p) {
            p = p->next;
            q = q->next;
        }
        return q;
    }
};
    0 赞同 0 条回复
  • 青木 普通 2022年10月21日 下午8:31

    简单实现之前文中的做法

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null){
            return head;
        }
        ListNode p = head;
        ListNode q = head;
        //让另一个指针跑到对应位置
        while(k > 1){
            p = p.next;
            k -= 1;
        }
        //迭代
        while(p.next != null){
            p = p.next;
            q = q.next;
        }
        return q;
    }
}
    0 赞同 0 条回复
  • lobort 普通 2022年10月21日 下午8:27

    “`java
    “`java
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
    //如果头节点为0 k小于等于0 返回空
    if( head == null || k <= 0){ return null; } //定义前后指针 ListNode fast = head; ListNode slow =head; //先让前指针走k步 while(fast !=null && k >0 ){
    fast = fast.next;
    k–;

        }
    while(fast!= null){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

    }

    0 赞同 0 条回复
  • 一只骆驼 普通 2022年10月21日 下午8:25

    让一个指针temp先走k步,再让temp与head一起移动,当temp到链表尾的时候,head到倒数第K个节点

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head==null) return head;
        ListNode temp = head;
        while(k>0){
            temp=temp.next;
            k--;
        }
        while(temp!=null){
            temp=temp.next;
            head=head.next;
        }
        return head;
    }
}
    0 赞同 0 条回复
  • 天然 普通 2022年10月21日 下午8:21

    让cur先走k-1，然后tex和cur一起走，退出条件 cur.next=None

    class Solution(object):
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        cur = head
        tex = head


<pre><code>    for i in range(k-1):
        cur= cur.next

    while cur.next!=None:
        tex = tex.next
        cur= cur.next
    return tex
</code></pre>
    0 赞同 0 条回复
  • 西西弗斯的石头 永久会员 2022年10月21日 下午8:21

    简单

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null) return null;
        ListNode i = head;
        ListNode j = head;
        while(k != 1){
            j = j.next;
            k--;
        }
        while(j.next!=null){
            i = i.next;
            j = j.next;
        }
        return i;
    }
}
    0 赞同 0 条回复
  • zjl 普通 2022年10月21日 下午8:13

    双指针，p1走K步，p1,p2 再同步走

        public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode p1 = head;
        ListNode p2 = head;
        while(k-- != 0){
            p1 = p1.next;
        }
        while(p1 != null){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }
    0 赞同 0 条回复
  • 1ue1uekin8 普通 2022年10月21日 下午8:13

    随便写

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode tmp = head;
        ListNode ans = head;
        int length = 0;
        while (tmp.next!=null) {
            length+=1;
            tmp = tmp.next;
        }
        for(int i = 0;i<=length-k;i++){
            ans = ans.next;
        }
        return ans;
    }
}
    0 赞同 0 条回复
  • 王艺超 普通 2022年10月21日 下午8:12

    因为知道要用快慢指针，所以倒没遇到什么坑，就注意 i 应该从1开始

    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if(head == NULL)
            return NULL;

        ListNode *quike = head;
        ListNode *slow = head;

        for(int i = 1;i < k;i++)
        {
            if(quike == NULL)
                return NULL;
            quike = quike->next;
        }
        while(quike->next != NULL)
        {
            quike = quike->next;
            slow = slow->next;
        }
        return slow;
    }
};
    0 赞同 0 条回复
  • 忆霁昕 永久会员 2022年10月21日 下午8:10

    双指针

    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    0 赞同 0 条回复
  • Whatever 永久会员 2022年10月21日 下午7:52

    快慢指针的运用

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head,slow = head;
        for(int i = 0;i < k;i++){
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
    0 赞同 0 条回复
  • 宁 永久会员 2022年10月21日 下午7:48

    注意本题从1开始计数

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode left = head;
        ListNode right = head;
        for(int i = 0; i < k; i++){
            right = right.next;
        }
        while(right != null){
            left = left.next;
            right = right.next;
        }
        return left;
    }
}
    0 赞同 0 条回复

# 回答此问题

后才能回答