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

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

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

要求：

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

shuaidi
338 97

共以下 97 个回答

  • 慎言 永久会员 2023年7月16日 下午2: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) {
    ListNode* pre=head;
    ListNode* tmp=head;
    while(k–) tmp=tmp->next;
    while(tmp){
    pre=pre->next;
    tmp=tmp->next;
    }
    return pre;
    }
    };

    0 赞同 0 条回复
  • ZJS 永久会员 2023年7月9日 上午10:55

    方法：快慢指针
    时间复杂度O(n)
    空间复杂度为O(1)

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

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

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

        return slow;
    }
}
    0 赞同 0 条回复
  • 冬 普通 2023年7月9日 上午10:05

    倒数第k个=正数第 总个数+1-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 helper=head;
    int num=0;
    while(helper.next!=null){
    helper=helper.next;
    num++;
    }
    ListNode cur=head;
    for(int i=1;i<=num+1-k;i++){
    cur=cur.next;
    }
    return cur;
    }
    }

    0 赞同 0 条回复
  • 一琬人间烟火 普通 2023年7月7日 下午9:38

    c++：
    快慢指针
    class Solution {
    public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
    ListNode* fast=head;
    ListNode* slow=head;
    while(k–){
    fast=fast->next;
    }
    while(fast!=NULL){
    fast=fast->next;
    slow=slow->next;
    }
    return slow;
    }
    };

    0 赞同 0 条回复
  • CaCO3 永久会员 2023年7月7日 下午9:21

    ”’java
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
    //快慢指针
    ListNode slow = head;
    ListNode fast = head;
    for(int i = 0;i < k;i++){
    fast = fast.next;
    }
    while(fast != null){
    slow = slow.next;
    fast = fast.next;
    }
    return slow;
    }
    };
    时间复杂度O(n)
    空间复杂度O(1)

    0 赞同 0 条回复
  • 北京西 普通 2023年7月5日 下午11:37

    打卡

    struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    struct ListNode *i,*j;
    i=head;
    j=head;
    for (int nodeNumber=1;nodeNumbernext;
    while (i->next!=NULL)
    {
        i=i->next;
        j=j->next;
    }
    return j;
}

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

    1 赞同 0 条回复
  • ᯤ 普通 2023年7月4日 下午10:47

    快慢指针

    public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode slow = head, fast = head;
    for (int i = 1 ; i < k ; i ++) {
        fast = fast.next;
    }
    while(fast.next != null) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}
    0 赞同 0 条回复
  • cute. 普通 2023年7月3日 下午8:59

    思路：快慢指针 + 虚拟头结点

    var getKthFromEnd = function(head, k) {
    let dummy = new ListNode(0, head);
    let fast = slow = dummy;
    let index = k - 1;
    while(index--) {
        fast = fast.next;
    }
    while(fast.next !== null && slow.next !== null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
};
    0 赞同 0 条回复
  • mpweixin用户 永久会员 2023年7月1日 上午12:29

    代码

    class Solution {
    public static ListNode ans=null;
    public int getNode(ListNode head,int k){
        if(head==null){
            return 0;
        }
        int a=getNode(head.next,k);
        if(k==a){
            ans=head.next;
        }
        return a+1;
    }
    public ListNode getKthFromEnd(ListNode head, int k) {
        ans=head;
        getNode(head,k);
        return ans;
    }
}
    0 赞同 0 条回复
  • 与你同行 普通 2023年6月30日 下午5:14

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

    /**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getKthFromEnd(head *ListNode, k int) *ListNode {
    if head == nil || k <= 0{
        return head
    }

    //定义一个快指针fast，先走k个节点
    //定义一个慢指针slow,等fast走k个节点后，一起出发
    //1,2,3,4,5,6 k=2  ==》期待返回：5,6
    //fast:3,4,5,6 slow:1,2,3,4,5,6
    //fast:4,5,6 slow:2,3,4,5,6
    //fast:5,6 slow:3,4,5,6
    //fast:6 slow:4,5,6
    //fast:nil slow:5,6

    fast := head
    slow := head
    //fast先走k个节点
    for i := 0; i < k; i++ {
        fast = fast.Next
    }

    //等fast走k个节点后，一起出发
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    return slow
}
    0 赞同 0 条回复
  • 招舟子 普通 2023年6月29日 下午8:30 
    /**
 * 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 pre = head,rear = head;
        while(k!=0){
            rear = rear.next;
            k--;
        }
        while(rear!= null){

            rear = rear.next;
            pre = pre.next;
        }
        return pre;
    }
}

    简单

    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月28日 上午11:29

    ”’java
    /**
    * 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 pre = head;
    ListNode post = head;
    for(int i = 0; i < k && post != null; i++, post = post.next) ;
    if(post     null) {
    System.out.println(“k的值大于链表的长度”);
    return head;
    }
    while(post != null) {

            post = post.next;
        pre = pre.next;
    }
    return pre;
}

    }
    ”’
    时间复杂度O(N), 空间复杂度O(1)

    0 赞同 0 条回复
  • 昂立的狼 普通 2023年6月28日 上午10:47

    时间复杂度O(n)
    空间复杂度O(1)
    使用快慢指针，当快指针的next指向为None时，则到达最后k个节点，输出慢指针

    class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        if head.val is None:
            return head
        t = head
        for i in range(1,k):
            t = t.next
            if t.next is None:
                return head
        while t.next is not None:
            head = head.next
            t = t.next
        return head
    0 赞同 0 条回复
  • 浅伤 永久会员 2023年6月28日 上午10:32

    时间复杂度O(n)
    空间复杂度O(1)
    先判断是否为空链表
    设置快慢指针temp，pre
    先将temp移到第k个节点
    然后同步向后走，当temp为空时遍历完成，此时pre只想倒数第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) {
        if(head == null){
            return null;
        }

        ListNode temp = head.next, pre = head;

        for(int i=0; i<k-1; i++){
            temp = temp.next;
        }

        while(temp != null){
            temp = temp.next;
            pre = pre.next;
        }

        return pre;

    }
}
    0 赞同 0 条回复
  • 淡色 花樱 普通 2023年6月28日 上午9:48

    ““java
    class Solution{
    public ListNode getKthFromEnd(ListNode head,int k){
    if(head null)
    {
    return null;
    }
    ListNode fast = head, slow = head;
    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(n)
    空间复杂度0(1)
    fast比slow多走k步，然后slow和fast一起走，当fast等于null时，slow正好是倒数第k个节点

    0 赞同 0 条回复
  • 橙子陈 普通 2023年6月28日 上午12:06 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (null == head) {
            return null;
        }

        // 定义快慢指针
        ListNode fast = head;
        ListNode slow = head;

        // 移动快指针k步
        for (int i = 0; i < k; i++) {
            if (null == fast) {
                return null;
            }
            fast = fast.next;
        }

        // 同时移动快慢指针，当快指针指向空时，慢指针指向倒数第k个节点
        while (null != fast) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }
}

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

    0 赞同 0 条回复
  • 大大 普通 2023年6月27日 下午6:20

    C++实现：//思路转化成正着数第几个
    //时间复杂度O(n)

    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {//转化成正数第几个节点m-k+1
      if(!head)
      return NULL;
      ListNode* temp=head;
      int m=1;
      while(temp->next!=NULL){
          temp=temp->next;
          m++;
      }
      temp=head;
      for(int i=1;i<m-k+1;i++){
           temp=temp->next;
      }
      return temp;      
    }
};
    0 赞同 0 条回复
  • Lucky 普通 2023年6月27日 下午3:31

    Python 实现
    class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
    former, latter = head, head
    for _ in range(k):
    former = former.next
    while former:
    former, latter = former.next, latter.next
    return latter

    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月26日 下午9:44

    双指针，一个指针先走k步，之后两指针同时移动直到靠后的指针到链表末尾
    时间复杂度: O(n)
    空间复杂度：O(1)
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode pre = head;
    ListNode now = head;
    for(int i = 1 ; i<k ; i++){
    now = now.next;
    }

        while(now.next != null){
        pre = pre.next;
        now = now.next;
    }

    return pre;

}

    }

    0 赞同 0 条回复
  • 泡芙 永久会员 2023年6月26日 下午5:42

    如果链表长度为 n，那么只要一个指针移动 n – k 次就能找到倒数第 k 个节点
    双指针，fast先移动k个节点，然后fast和slow同时移动，最后返回slow

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

        if (head == null) {
            return null;
        }

        // 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;

    }
}
    0 赞同 0 条回复
  • dys 普通 2023年6月26日 下午4:43

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
    if (head null){
    return head;
    }
    ListNode curr = head;
    ListNode pre = head;
    for(int i = 0; i < k; i++){
    if (pre     null) return null;
    pre = pre.next;
    }
    while(pre != null){
    pre = pre.next;
    curr = curr.next;
    }
    return curr;
    }
    }
    跟大家一样用的双指针解决这个问题，时间复杂度curr需要走n次，所以是O(n)，空间复杂度使用常数大小的额外空间，所以是O(1)

    0 赞同 0 条回复
  • Yangon 普通 2023年6月25日 上午11:10 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null){
            return null;
        }

        ListNode low = head;
        ListNode fast = head;
        for(int i = 1; i < k; i++){
            fast = fast.next;
        }
        while(fast.next != null){
            fast = fast.next;
            low = low.next;
        }
        return low;

    }
}

    快慢指针

    0 赞同 0 条回复
  • HU 普通 2023年6月24日 下午6:06

    有三种情况：
    + 链表为空，则返回空。
    + 链表长度小于k，则返回空。
    + 不是上述两种情况，则接着往后。

    /**
 * 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) {
    // 如果链表为空，则返回空
    if(head === null) {
        return null;
    }

    // 定义快慢指针
    let fast = head, slow = head;

    // 先让fast走k步
    for (let i = 0; i < k; i++) {
        // 如果fast为null，则返回null
        if(fast === null) {
            return null;
        }

        fast = fast.next;
    }

    // 让fast和slow同时走，一直走到fast为null为止
    while (fast !== null) {
        fast = fast.next;
        slow = slow.next;
    }

    return slow;
};

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

    0 赞同 0 条回复
  • Gracelyne 普通 2023年6月24日 下午3:05 
    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *fast = new ListNode(-1), *slow = new ListNode(-1); //快指针慢指针
        fast->next = head;
        slow->next = head;
        for(int i=0; i<k; i++){
            fast->next = fast->next->next;
        }
        while(fast->next != NULL){
            fast->next = fast->next->next;
            slow->next = slow->next->next;
        }
        return slow->next;
    }
};
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月23日 下午8:36

    使用快慢指针，注意快指针先走K节点，然后快指针走完链表代表fast null

    /**
 * 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;
        }
        if (k<=0) {
            return head;
        }
        ListNode fastNode = head;
        ListNode slowNode = head;
        while(k>0 && fastNode!=null) {
            fastNode = fastNode.next;
            k--;
        }

        while(fastNode != null) {
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }

        return slowNode;

    }
}
    0 赞同 0 条回复
  • WhyBeBubble 普通 2023年6月22日 下午5:24 
    C++实现
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
       ListNode *slow, *fast;
        slow = fast = head;
        while(fast && k > 0) {
            fast = fast->next;
            k--;
        }
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};
    0 赞同 0 条回复
  • Yodl. 普通 2023年6月22日 上午11:58 
    /**
 * 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* p=head;
        ListNode* q=head;
        int i=0;
        while(i!=k&&q!=NULL)
        {
            q=q->next;
            i++;
        }
        if(q==NULL)
        {
            return p;
        }
        else
        {
            while(q!=NULL)
            {
                q=q->next;
                p=p->next;
            }
            return p;
        }
    }
};

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

    0 赞同 0 条回复
  • 短某人。 永久会员 2023年6月22日 上午12:25

    打卡

    class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        former, latter = head, head
        for _ in range(k):
            former = former.next
        while former:
            former, latter = former.next, latter.next
        return latter
    0 赞同 0 条回复
  • 等待 普通 2023年6月21日 下午11:08

    java语言，双指针
    public ListNode getKthFromEnd(ListNode head, int k) {
    //非空判断
    if (head null){
    return null;
    }
    // 定义头节点
    ListNode headNode = new ListNode();
    headNode.next = head;
    // 定义快指针
    ListNode fastNode = headNode;
    // 定义慢指针
    ListNode slowNode = headNode;
    // 快指针多走K步
    while (k-1!=0){
    fastNode = fastNode.next;
    k–;
    }
    //慢指针找到对应位置
    while(fastNode.next!=null){
    slowNode = slowNode.next;
    fastNode = fastNode.next;
    }
    return slowNode;
    }
    空间复杂度O(1)
    时间复杂度O(n)

    0 赞同 0 条回复
  • 地平线真勇敢 普通 2023年6月21日 下午10:30 
    //代码Java实现，思路：双指针、fast指针走k步，然后fast和low指针一块走，等fast指针走到null时，low指针指向倒数第k个节点
public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null){   //对头节点判空处理
            return null;
        }
        ListNode fast = head;
        ListNode low = head;
        int i = 0;
        while(i<k){
            if(fast == null){   //考虑节点为空导致节点异常
                return null;
            }
            fast = fast.next;
            i++;    //循环变量自增
        }
        while(fast!=null){
            fast = fast.next;
            low = low.next;
        }
        return low;
    }

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

    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月21日 下午8:35 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //查找倒数K个结点，将指针移动N-K次
        //pre指针先移动K次，after再和pre同时移动。直至pre=null
        ListNode pre = head;
        ListNode after = head;
        for(int i = 1;i <= k;i++){
            pre = pre.next;
        }
        while(pre != null){
            pre = pre.next;
            after = after.next;
        }
        return after;
    }
}
//解法二
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //查找倒数K个结点，将指针移动N-K次（双指针规律）
        if(head == null){
            return head;
        }
        int count = 1;
        ListNode p = head;
        while(p.next != null){
            p = p.next;
            count++;
        }
        p = head;
        for(int i = 1;i <= count-k;i++){
            p = p.next;
        }
        return p;
    }
}

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

    0 赞同 0 条回复
  • mpweixin用户 永久会员 2023年6月21日 下午6:53

    打卡

    var getKthFromEnd = function(head, k) {
    // 特殊情况
    if(head == null)  {
        return head;
    }
    // 使用快慢指针
    let slow = head;
    let fast = head;
    let tempIndex = k;
    // 快指针先移动到k个节点的位置
    while(tempIndex > 0 && fast != null){
        fast = fast.next;
        tempIndex--;
    }

    // 开始同时移动快慢指针，找到倒数第k个节点
    while(fast != null){
        fast = fast.next;
        slow = slow.next;
    }

    // 此时slow指向的节点就是倒数第k个节点
    return slow;
};
    0 赞同 0 条回复
  • TT 永久会员 2023年6月21日 下午5:33

    使用双指针

    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 条回复
  • 往远处看 普通 2023年6月21日 下午1:24

    解题思路

    单指针实现找到链表倒数第K个节点，首先通过设置一个指针，指针每移动一次节点个数+1，统计出节点的个数，然后根据倒数第k个数=n-k+1,按照这个从头往后遍历到倒数第k个数，遍历一个节点n-1，当n的值和k的值相同的时候就是指向了该节点

    代码

    /**
 * 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* node;
        node = nullptr;
        int n = 0;
        for(node = head;node;node = node->next)
        {
            n = n + 1;
        }
        for(node = head; n>k;node = node->next)
        {
            --n;
        }
        return node;

    }
};
    0 赞同 0 条回复
  • 哈哈哈哈开开心心 普通 2023年6月21日 上午6:31

    时间复杂度O(n)

    # 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:
        if not head:
            return None

        fast = head
        while k > 0:
            fast = fast.next
            k -= 1

        slow = ListNode()
        slow.next = head

        while fast:
            fast = fast.next
            slow = slow.next

        return slow.next
    0 赞同 0 条回复
  • CV大神 普通 2023年6月21日 上午12:09 
     /**
     * @param k 查找倒数第k个节点
     * @return
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        //获取长度
        int length = getLength(head);
        if(length < k){
            return null;
        }
        ListNode temp = head;
        //循环找到对应接地那
        for (int i=1;i

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

    0 赞同 0 条回复
  • 未来已来~ 普通 2023年6月20日 下午9:37 
    /**
 * Java 代码
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路:用快慢指针，快指针先走k(输入的数字)个节点，然后 快、慢指针一起走,快指针走到结尾(null),慢指针所在节点即为要查找的节点(删除指定结点也是一样的思路)
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        // 1.判断空链表情况
        if (head == null) {
            return null;
        }
        // 2. 思路,快慢指针
        ListNode fast = head;
        ListNode slow = head;
        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;
    }
}

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

    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月20日 下午9:19 
    # 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:
        if not head:
            return None
        if not head.next:
            return head
        fast = head
        slow = head
        cnt = k
        while cnt > 0:
            fast = fast.next
            cnt -= 1
        while fast:
            slow, fast = slow.next, fast.next
        return slow
    0 赞同 0 条回复
  • Tlhey 普通 2023年6月20日 下午8:01

    // 语言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) {
    int cnt=1;
    ListNode* node0 = head;
    while(node0->next!=nullptr){
    node0=node0->next;
    cnt++;
    }
    for(int i=1;i<=cnt-k;i++)
    head=head->next;
    return head;
    }
    };

    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月20日 下午7:05 
    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;
    }
}

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

    0 赞同 0 条回复
  • 孙宏民 普通 2023年6月20日 下午5:59 
    public ListNode getKthFromEnd(ListNode head, int k) {
            if (head == null) {
                return null;
            }
            if (k == 0) {
                return head;
            }

            ListNode slow = head;

            int index = 0;
            while (head.next != null) {
                if ((index + 1) > k) {
                    slow = slow.next;
                }
                head = head.next;
                index++;
            }

            return slow;
        }

    通过快慢指针来完成函数，设置慢指针指向head，设置当前遍历的索引index=0，当满足条件 index + 1 > k 时，慢指针开始移动，slow = slow.next , 当快指针到达链表末尾时 head.next = null ，返回slow即为所求
    时间复杂度 O(n) 空间复杂度O(1)

    0 赞同 0 条回复
  •  普通 2023年6月20日 下午5:45 
    //剑指 Offer 22. 链表中倒数第k个节点
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode right = head;
        for(int i=0;i<k;i++){
            right = right.next;
        }
        ListNode left = head;
        while(right != null){
            right = right.next;
            left = left.next;
        }
        return left;
    }
}
    0 赞同 0 条回复
  • mpweixin用户 永久会员 2023年6月20日 下午4:56

    /**
    * 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 indexNode = head;
    int length = 0;
    while(indexNode != null) {
    length++;
    indexNode = indexNode.next;
    }
    int counter = 1;
    while(head != null){

            if(counter + k == length + 1){ //正向序号与反向序号的相加值总为全长度+1，可以此为判断
            break;
        }
        head = head.next;
        counter += 1;
    }
    return head;


}

    }

    0 赞同 0 条回复
  • &Camille 普通 2023年6月20日 下午2:58

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode temp=head, latter=head;

        //temp指针移动K位
    for(int i=0;i<k;i++){
        temp=temp.next;
    }

    //双指针相同速度移动，latter慢K位，temp到末尾时，latter为倒数第K位
    while(temp!=null){
        temp=temp.next;
        latter=latter.next;
    }
    return latter;

}

    }

    0 赞同 0 条回复
  • 断舍离 永久会员 2023年6月20日 下午2:31 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //相当于一个标志节点，让该标志节点和头节点一起向后遍历
        ListNode flag = head;
        for(int i = 0; i < k; i++){
            flag = flag.next;
        }

        //当flag==null时，此时同步往后遍历的head就是要找的节点
        while (flag != null){
            flag = flag.next;
            head = head.next;
        }

        return head;
    }
}
    0 赞同 0 条回复
  • BOZ 普通 2023年6月20日 下午2:28

    双指针，时间复杂度O(n)，空间复杂度O(1)

    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *fast_ptr = head, *slow_ptr = head;
        // fast_ptr is k node ahead of slow_ptr
        while(k--) {
            if (fast_ptr != NULL) fast_ptr = fast_ptr->next;
            else return fast_ptr;
        }
        // enumerate the list
        while(fast_ptr != NULL) {
            fast_ptr = fast_ptr->next;
            slow_ptr = slow_ptr->next;
        }
        return slow_ptr;
    }
};
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月20日 下午12:03

    剑指offer22 暴力解法 时间复杂度O(n) 空间复杂度O(1)

    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        int n = 0;
        ListNode *p = head;
        ListNode *result = head;
        while(p != NULL){
            n++;
            p = p -> next;
        } 

        for(int i = 0; i < n - k; i++){
            result = result -> next;
        }
        return result;
    }
};

    剑指offer 双指针法 时间复杂度O(n) 空间复杂度O(1)

    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if(head == NULL) return head;
        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 条回复
  • mpweixin用户 普通 2023年6月20日 上午11:26 
    # 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:
        if not head:
            return None

        slow = head
        fast = head

        step = k - 1
        while step:
            fast = fast.next
            step -= 1

        while fast.next:
            slow = slow.next
            fast = fast.next
        return slow

    双指针法。使用slow指针和fast指针分别指向头节点和头节点的后（k-1)个节点。当fast指针指向链表的最后一个节点时，slow指针指向链表的倒数第k个节点。

    0 赞同 0 条回复
  • 小柒叻 普通 2023年6月20日 上午10:56

    剑指 Offer 22. 链表中倒数第k个节点
    双指针删除节点

    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
    ListNode* fast=head;
    ListNode* slow=head;
    if(head==nullptr)
    return nullptr;
    for(int i=0;i<k;i++){
        if(fast==nullptr)
        return nullptr;
        else
        fast=fast->next;
    }
    while(fast!=nullptr){
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
    }
};
    0 赞同 0 条回复
  • 名字什么的好麻烦 普通 2023年6月20日 上午10:38

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

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode cur=head;
        int l=0;
        while(cur!=null){
            l++;
            cur=cur.next;
        }
        l=l-k;
        while((l--)!=0){
            head=head.next;
        }
        return head;
    }
}
    0 赞同 0 条回复
  • 硬核洋葱 普通 2023年6月20日 上午9:57 
    /**
 * 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* fast = head;
        while(k){
            --k;
            fast = fast->next;
        }

        ListNode* ans = head;
        while(fast){
            fast = fast->next;
            ans = ans->next;
        }
        return ans;
    }
};

    时间复杂度 O(n)，空间复杂度 O(1)
    双指针

    0 赞同 0 条回复
  • 花老爷 普通 2023年6月20日 上午8:58

    快慢指针
    时间：O(n)
    空间：O(1)

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        for (int i = 1; i < k; i++) {
            fast = fast.next;
        }
        ListNode low = head;
        while (fast.next != null) {
            low = low.next;
            fast = fast.next;
        }
        return low;
    }
}
    0 赞同 0 条回复
  • 跋扈疙瘩汤 普通 2023年6月20日 上午8:38

    奇怪，为啥没有提交上

    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        vector<ListNode*> nums(100000);
        int count = 0;
        while (head) {
            nums[count] = head;
            head = head->next;
            count++;
        }
        return nums[count-k];
    }
};
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月20日 上午3:52

    c++
    使用前后指针，前指针先移动k步。
    然后前后指针同时移动，保证前指针在空的时候，后指针在倒数第k个上
    TC: O(n)
    SC: O(1)

    class Solution {
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) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};
    0 赞同 0 条回复
  • baoyou 普通 2023年6月19日 下午11:52 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null) {
            return null;
        }
        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;
    }
}

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

    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月19日 下午11:41 
    struct ListNode* getKthFromEnd(struct ListNode* head, int k){
   struct ListNode*fast=head,*slow=head;
   if(head==NULL)
   {
       return head;//特殊情况，链表不存在
   }
   for(int i=0;i<k;i++)
   {
       if(fast!=NULL)
       {
           fast=fast->next;
       }
   }
   while(fast!=NULL)//快慢指针都往后移动，条件表达式是指当前fast指针不为空，则执行while循环
   {   
       fast=fast->next;
       slow=slow->next;
   }
  return slow;
}

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

    0 赞同 0 条回复
  • 　　　　　　　　 普通 2023年6月19日 下午11:40 
    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* f=head,*s=head;
        while(k--)f=f->next;
        while(f){
            f=f->next;
            s=s->next;
        }
        return s;
    }
};

    【时间O(n),空间O(1)】
    快指针先走k步
    快慢指针一起走
    当快指针走到末尾时，慢指针则走到倒数k个节点

    0 赞同 0 条回复
  • Bello~ 普通 2023年6月19日 下午11:39

    时间复杂度O（n）
    空间复杂度O（1）

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        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 条回复
  • yxy 普通 2023年6月19日 下午11:30 
    /**
 * 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* fast = head;
        ListNode* slow = head;
        while(fast&&k--)
        {
            fast=fast->next;
        }
        while(fast)
        {
            fast=fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

    时间复杂度On
    空间O1

    0 赞同 0 条回复
  • 大鑫啊 普通 2023年6月19日 下午11:22

    时间复杂度：O(n)
    空间复杂度：O(1)
    1、先判断链表是否为空
    2、再创建快结点和慢结点
    3、快结点先走k步，同时判断快结点是否为空，为空则返回null
    4、在快结点不为空时，快慢结点一起往前走，最后返回慢结点即可

    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;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
    0 赞同 0 条回复
  • 残月冷骄阳 普通 2023年6月19日 下午11: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) {

<pre><code>    ListNode fasterNode = head;
    ListNode afterNode = head;

    //双指针法，两个指针之间的距离是k-1，当快指针到达末尾的时候，满指针指向的节点就是倒数第n个节点。
    for (int i=0; i < k-1 ; i++){
        if (fasterNode==null){
            return null;
        }
        fasterNode = fasterNode.next;
    }

    while(fasterNode.next!=null){
        fasterNode = fasterNode.next;
        afterNode = afterNode.next;
    }

    return afterNode;
}

}
    0 赞同 0 条回复
  • 彦，，# 普通 2023年6月19日 下午11:19

    先设定符合题目的链表长度，再将尾指针向后移，就是内存占用有点大

    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if(k<= 0) return head;
        ListNode* last = head;
        int i = 0;
        for(i = 0;i < k-1; i ++)
        {
            if(last->next)
            {
                last = last->next;
            }else{
                return NULL;
            }
        }
        while(last->next)
        {
            last = last->next;
            head = head->next;
        }
        return head;
    }
};
    0 赞同 0 条回复
  • Tral-JQ 普通 2023年6月19日 下午11:11 
    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {

 //快慢指针法——快指针先走k步，指向队尾；慢指针指向队头
    ListNode* fast = head;
    ListNode* slow = head;

    while(k>0){
        fast = fast->next;
        k--;
    }

    while(fast!= nullptr){
        fast = fast->next;
        slow = slow->next; 
    }
    return slow;
}
};
    0 赞同 0 条回复
  • 别恰冰水🧊 永久会员 2023年6月19日 下午11:09

    struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    if(head NULL){
    return NULL;
    }

    struct ListNode* fast = head;
struct ListNode* slow = head;

for(int i=0;i<k;i++){//fast先走K步
    if(fast == NULL){
        return NULL;
    }
    fast = fast->next;
}

while(fast!=NULL){
    fast = fast->next;
    slow = slow->next;//fast和slow同时向后移动
}
return slow;

    }

    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月19日 下午11:09

    正着走k个之后，再走到头的步数n n+k就是总长度 第n个就是倒数第k个

    “`C#
    public 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 == null){
            return null;
        }
        fast = fast.next;
    }

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

    return slow;
}

    }

    “`

    0 赞同 0 条回复
  • Jerry 普通 2023年6月19日 下午11:04 
    public class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
    public ListNode deleteTheKNode(ListNode head, int k) {
        ListNode former = head, latter = head;
        // former指针先往前走k步
        for (int i = 1; i <= k; i++) {
            former = former.next;
        }
        // 再让former、latter一起走，直到former走到链表尾部为止
        while (former != null) {
            former = former.next;
            latter = latter.next;
        }
        // 这时候latter就是倒数第k个节点
        return latter;
    }
}

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

    0 赞同 0 条回复
  • 张君雅小妹妹 普通 2023年6月19日 下午10:58

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

        public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        while(k-- > 0){  // 加上fast == null的判断会更好
            fast = fast.next;
        }

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

        return slow;
    }
    0 赞同 0 条回复
  • Sexypig. 普通 2023年6月19日 下午10:50

    代码：

    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if(!head)
            return head;
        ListNode* fast=head;
        ListNode* slow=head;
        for(int i=1;i<k;++i)
        {
            fast=fast->next;
        }
        while(fast->next)
        {
            fast=fast->next;
            slow=slow->next;
        }
        return slow;
    }
};
    0 赞同 0 条回复
  • 怀瑾 永久会员 2023年6月19日 下午10:41

    C++
    执行用时：
    8 ms
    内存消耗：
    10.3 MB
    链表中倒数第K个节点：
    双指针的方式：
    设定一个指针指向该指针+k的节点处，使两个指针进行遍历，当快指针遍历完成后，直接返回慢指针即可。

    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* headk=head;
        while(k>1){
            headk=headk->next;
            k--;
        }
        while(headk->next!=NULL){
            headk=headk->next;
            head=head->next;
        }
        return head;
    }
};
    0 赞同 0 条回复
  • zll 普通 2023年6月19日 下午10:39

    思路：双指针p、q，p比q先行k步
    注意：k大于链表长度的情况
    时间复杂度：O（n）
    空间复杂度：O（1）

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* getKthFromEnd(struct ListNode* head, int k){
        if(head==NULL){
            return NULL;
        }
        struct ListNode *p,*q;
        p=head;
        q=head;
        for(int i=0;inext==NULL){
                return NULL;
            }
            p=p->next;
        }
        while(p->next!=NULL){
            p=p->next;
            q=q->next;
        }
        return q;
}
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月19日 下午10:36

    思路：快慢指正思想，让快指针先走k步，然后快慢指针以前走，以慢指针为有节点返回结果链表。

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

        for (int i = 0; i < k; i++){
            if (fast == null) {
                return null;
            }
            fast = fast.next;
        }

        while (fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow; 
    }
}
    0 赞同 0 条回复
  • 钱杰 普通 2023年6月19日 下午10:35

    class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
    fast,slow=head,head
    for i in range(k):
    if fast:
    fast=fast.next
    else:
    return fast
    while fast:
    fast=fast.next
    slow=slow.next
    return slow

        '''
    1设置两个指针，一个是fast,一个是slow,都指向头结点head
    2 k表示fast比slow多走的步数，这里是让fast先走k步，如果一下子走到底了，返回此时fast的指向及其之后的内容，也就是空
    3当走完k步，我们就得让fast和slow走相同的步数，直到fast为空，就返回slow的指向及其之后的内容，也就是剩余的k个节点
    #时间复杂度：O(n)，空间复杂度：O(1)
    '''
    0 赞同 0 条回复
  • 江畅 普通 2023年6月19日 下午10:22

    “`c++
    class Solution {
    public:
    // 快慢指针
    // 时间复杂度 O(N)，需遍历一次链表 N 个节点
    // 空间复杂度 O(1)
    ListNode* getKthFromEnd(ListNode* head, int k) {
    ListNode* slow = head;
    ListNode* fast = head;

        // 快指针先走 k 步
    while (fast != nullptr && k > 0) {
        fast = fast->next;
        --k;
    }

    // 快慢指针同时走，快指针走到尾节点，满指针走到倒数第 k 个节点
    while (fast != nullptr) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}

    };

    “`

    0 赞同 0 条回复
  • 阿白 普通 2023年6月19日 下午10:12

    思路：双指针链表，快指针先走k步，然后快慢指针一起走，快指针走到最后时，慢指针走到倒数第k个
    复杂度：时间复杂度为O(n)，空间复杂度为O(1)

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

        ListNode fast = head , slow = head;
        for(int i = 1; i < k; i++){
            if(fast == null) {
                return null;
            }
            fast = fast.next;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;

    }
    0 赞同 0 条回复
  • 张开怀 普通 2023年6月19日 下午10:05

    c++实现
    class Solution {
    public:
    ListNode* getKthFromEnd(ListNode* head, int k){
    % 链表是否为空
    if(head nullptr) {
    return nullptr;
    }
    ListNode* fastIndex = head;
    ListNode* slowIndex = head;
    % 快指针先走k步
    for(int i=0; i<k; i++){
    if(fastIndex     nullptr) {
    return nullptr;
    }
    fastIndex = fastIndex->next;
    }
    while(fastIndex != nullptr){
    fastIndex = fastIndex->next;
    slowIndex = slowIndex->next;
    }
    return slowIndex;
    }
    }

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

    0 赞同 0 条回复
  • mpweixin用户 永久会员 2023年6月19日 下午9:56 
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null){
            return head;
        }

        ListNode fast = head;
        ListNode low = head;

        //fast走到第k个结点上
        while(k - 1 > 0 && fast != null){
            fast = fast.next;
            k--;
        }

        if(fast == null){
            //说明k范围不合法，超出了链表长度
            return null;
        }

        //fast走到最后一个结点上，此时low指向倒数第k个
        while(fast.next != null){
            fast = fast.next;
            low = low.next;
        }

        return low;
    }
    0 赞同 0 条回复
  • 哈哈哈 普通 2023年6月19日 下午9:51
    • 思路：使用快慢节点：head，fast。fast节点优先走k步，之后令快慢节点同时以1的步长进行行走，当fast节点为空之时，此时的head节点所在的位置刚好就是倒数第k个节点所在的位置。
    • 时间复杂度为O（n），空间复杂度为O（1）
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast=head;
        while(k!=0){
            fast=fast.next;
            k--;
        }
        while(fast!=null){
            fast=fast.next;
            head=head.next;
        }
        return head;
    }
}
    0 赞同 0 条回复
  • 小吕 普通 2023年6月19日 下午9:50

    c++实现
    ListNode* dummphead = new ListNode(0);
    dummphead->next = head;
    ListNode* result = dummphead->next;
    ListNode* slow = dummphead->next;
    while(result!=NULL&&k–)
    {
    result=result->next;
    }
    while(result!=NULL)
    {
    slow = slow->next;
    result=result->next;
    }
    return slow;

    0 赞同 0 条回复
  • ～ 普通 2023年6月19日 下午9:42

    c++代码
    class Solution {
    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!=nullptr){
    fast = fast->next;
    slow = slow->next;
    }
    return slow;
    }
    };

    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月19日 下午9:41 
    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *root=new ListNode(0);
        root->next=head;
        ListNode *slow=root;
        ListNode *fast=root;
        while(k--)
        {
            fast=fast->next;
        }
        while(fast!=nullptr)
        {
            fast=fast->next;
            slow=slow->next;
        }
        return slow;


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

};

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

    0 赞同 0 条回复
  • Tang 普通 2023年6月19日 下午9:30 
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        // 链表为空，返回null
        if (head == null) {
            return head;
        }
        // 将后一个节点置于第k个节点上
        ListNode tmp = head, pre = head;
        while (k != 0 && tmp != null) {
            tmp = tmp.next;
            k--;
        }
        // 如果tmp为空，说明链表没有k个节点，返回null
        if (k != 0 && tmp == null) {
            return null;
        }
        while (tmp != null) {
            tmp = tmp.next;
            pre = pre.next;
        }
        return pre;
    }
}

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

    0 赞同 0 条回复
  • * 普通 2023年6月19日 下午9:26

    js实现
    var getKthFromEnd = function(head, k) {
            // 双指针，指针距离是 k
            let pre = head;
            let next = head;
            for(let i = 1; i < k; i++) {
                    next = next.next;
            }
            while(next.next ! null) {
                    pre = pre.next;
                    next = next.next
            }
            return pre;
    };

    0 赞同 0 条回复
  • 濤.xiong 普通 2023年6月19日 下午9:21

    class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
    # 创建虚拟头部节点以简化删除过程
    dummy_head = ListNode(next = head)

        # 遍历列表并删除值为val的节点
    current = dummy_head
    while current.next:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next

    return dummy_head.next
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月19日 下午9:20

    使用C++实现
    使用双指针，快指针先走K步，然后快慢指针同时进行，快指针到尾部时，返回慢指针位置，二者中间刚好差K
    代码
    class Solution {
    public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
    ListNode * former = head;
    ListNode * later = head;
    while(former&&(k>0)){
    former = former->next;
    k–;
    }
    while(former){
    former = former->next;
    later = later->next;
    }
    return later;
    }
    };
    时间复杂度O(n)
    空间复杂度O(1)

    0 赞同 0 条回复
  • peach 普通 2023年6月19日 下午9:11

    思路

    • 使用双指针，快指针先走k步，使用while循环即可
    • 然后快慢指针同时走，当快指针走到链表末尾时，慢指针的位置即为要返回的节点
    • 时间复杂度O(n)，空间复杂度O(1)

    代码

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode f = head;
        ListNode s = head;
        while(k-- > 0){
            f = f.next;
        }
        while(f != null){
            f = f.next;
            s = s.next;
        }
        return s;
    }
}
    0 赞同 0 条回复
  • 悠若 普通 2023年6月19日 下午9:09

    双指针
    时间复杂度：O(n)，空间复杂度：O(1)

    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        for(int i = 0; i < k; i++) {
            fast = fast.next;
        }
        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
    0 赞同 0 条回复
  • 已断网的Blue 普通 2023年6月19日 下午9:07

    快慢指针 快指针先走k步 当快指针走到末尾 慢指针刚好走到倒数第K个结点

    “`c++
    class Solution {
    public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
    // write code here
    //快慢指针 快指针先走k步 当快指针走到末尾 慢指针刚好走到倒数第K个结点
    ListNode *fast = pHead;
    while(k–)
    {
    if(fast == NULL) return NULL;
    fast = fast->next;
    }
    while(fast){
    fast = fast->next;
    pHead = pHead->next;
    }
    return pHead;
    }
    };
    “`

    0 赞同 0 条回复
  • 伏月三十 普通 2023年6月19日 下午9:04

    打卡
    class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode fast=new ListNode(-1);
    fast=head;
    ListNode slow=new ListNode(-1);
    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 条回复
  • mpweixin用户 普通 2023年6月19日 下午9:03

    C++实现
    ··C++
    public ListNode deleteNode(ListNode head, int val) {
    ListNode temp=head;
    if(temp.nextnull)return null;
    if(temp.val    val){
    return temp.next;
    }
    while(temp.next!=null){
    if(temp.next.valval){
    temp.next=temp.next.next;
    return head;
    }
    temp=temp.next;
    }
    return null;
    }

    ···

    0 赞同 0 条回复
  • désire. 普通 2023年6月19日 下午9:00

    C++实现
    class Solution {
    public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
    if(head NULL) return head;
    ListNode* cur = new ListNode(0);
    cur->next = head;
    ListNode* tmp = new ListNode;
    tmp->next = head;
    int i = 0;
    int j;
    for(j = k;j > 0;j–){
    tmp = tmp->next;
    }
    while(tmp->next != NULL){
    cur = cur->next;
    tmp = tmp->next;
    }
    return cur->next;
    }
    };

    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月19日 下午8:56

    java实现

     public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode slow=head;
        ListNode quick=head;
        for(int i=0;i<k;i++){
            quick=quick.next;
        }
        while(quick!=null){
            quick=quick.next;
            slow=slow.next;
        }
        return slow;
    }

    时间复杂度为n,空间复杂度为1.
    思路：先让quick结点走k步，之后当quick为null，即走完的时候，slow结点就是倒数的第k个结点

    0 赞同 0 条回复
  • Dsjh 普通 2023年6月19日 下午8:45

    c++ 实现
    class Solution {
    public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
    ListNodeslow = head;
    ListNode    fast = head;
    k–;
    while(k–){
    fast = fast->next;
    }
    while(fast->next){
    slow = slow->next;
    fast = fast->next;
    }
    return slow;
    }
    };

    0 赞同 0 条回复
  • 雨落圆荷 普通 2023年6月19日 下午8:37

    class Solution{
    public ListNode(ListNode head，int k ){
    if(headnull)｛
    return null;
    ｝
    ListNode fast=head，slow=head;
    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
    }
    }
    时间复杂度：O(n)
    空间复杂度：O(1)

    0 赞同 0 条回复
  • Ming 普通 2023年6月19日 下午8:36

    这里是Ming的打卡：
    不涉及增删改，不建立虚拟头结点也能解决
    解题方法：双指针，快的先走k步，之后咱俩就离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) {
        if(head == null) return head;
        //双指针法，快的先走k步，之后快慢同步走
        ListNode fast = head;
        ListNode slow = head;
        for(int i = 0; i < k; i++) {
            fast = fast.next;
        }
        //fast=3 4 5 null
        //slow=1 2 3 4
        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年6月19日 下午8:34

    思路：双指针——快指针先走k步，然后快慢指针一起前进，当快指针达到尾部时，慢指针的位置即为倒数第k个节点的位置
    时间复杂度：O(n)，空间复杂度：O(1)

    class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        int count=1;
        ListNode* p=head->next;
        while(count<k){
            p=p->next;
            count++;
        }

        ListNode* q=head;
        while(p!=NULL){
            q=q->next;
            p=p->next;
        }
        return q;
    }
};
    0 赞同 0 条回复
  • Vow the vow。 普通 2023年6月19日 下午8:34

    快慢指针

    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode dummyNode = new ListNode();
        dummyNode.next = head;
        ListNode fast = dummyNode, slow = dummyNode;
        for(int i = 0; i < k && fast.next != null; i++){
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
    0 赞同 0 条回复
  • 行动派小彩笔 普通 2023年6月19日 下午8:31

    “`c++
    /**
    * Definition for singly-linked list.
    * struct ListNode {
    * int val;
    * ListNode *next;
    * ListNode(int x) : val(x), next(NULL) {}
    * };
    */
    /**
    * Definition for singly-linked list.
    * struct ListNode {
    * int val;
    * ListNode *next;
    * ListNode(int x) : val(x), next(NULL) {}
    * };
    */
    /*
    双指针，初始都直指向head,想让一个指针走k，这样两个指针之间就相差k步
    两个指针，在同时向下移动，直到先走的指针为NULL，后走的指针就指向倒数第k个节点
    */
    class Solution {
    public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
    if(head == NULL) return NULL;
    ListNode* cur = head,*ans = head;
    for(int i = 0;inext;
    else return NULL;
    }
    while(cur!=NULL)
    {
    cur = cur->next;
    ans = ans->next;
    }
    return ans;

    }

    };

    “`

    0 赞同 0 条回复

# 回答此问题

后才能回答