鱼旦普通 2023年8月7日上午11:15

<?php
class ListNode {
    public $val;
    public $next;

    public function __construct($val) {
        $this->val = $val;
        $this->next = null;
    }
}

function findKthToTail($head, $k) {
    $count = 0; // 初始化计数器为0
    $node = $head; // 将指针指向链表的头节点
    while ($node != null) { // 当指针不为空时继续遍历
        $count++; // 每遍历一个节点，计数器加一
        $node = $node->next; // 将指针移动到下一个节点
    }
    if ($count < $k) return null; // 如果链表长度小于k,返回null
    $k = $count - $k + 1; // 因为从1开始计数，所以需要将k转换为从0开始计数的位置
    $node = $head; // 将指针重新指向链表的头节点
    while ($node != null && $k > 0) { // 当指针不为空且k大于0时继续遍历
        $node = $node->next; // 将指针移动到下一个节点
        $k--; // k减1
    }
    return $node;
}

0 赞同 0 条回复

hyjob 普通 2023年8月3日下午3:32

【链表中倒数第k个节点】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* dummyHead = new ListNode(-1, head);
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        for (int i = 0; i < k; i ++) {
            fast = fast->next;
        }
        while (fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月30日下午10:34

打卡

/**
 * 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,*slow=head;
            for(;fast&&k>0;k--,fast=fast->next)
                ;
            for(slow=head;fast;fast=fast->next,slow=slow->next)
                ;
            return slow;


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

};

0 赞同 0 条回复

落洛普通 2023年7月19日下午6:01

打卡

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null){
            return head;
        }
        ListNode lHead = head;
        k--;
        while(k > 0){
            lHead = lHead.next;
            k--;
        }
        while(lHead.next != null){
            head = head.next;
            lHead = lHead.next;
        }
        return head;
    }
}

0 赞同 0 条回复

June 普通 2023年7月18日上午9:42

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getKthFromEnd(head *ListNode, k int) *ListNode {
    var fast *ListNode = head
    var slow *ListNode = head
    var i int = 0
    for i < k {
        fast = fast.Next
        i++
    } //快指针先走k步

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

0 赞同 0 条回复

夏唐普通 2023年7月17日下午3:42

打卡

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if head is None:
            return head
        fast = slow = head
        for i in range(k): # 判断k是否大于链表的长度
            if fast is None:
                return None
            fast = fast.next
        while fast is not None:
            fast = fast.next
            slow = slow.next
        return slow

0 赞同 0 条回复

李敏普通 2023年7月15日下午11:23

//代码
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++){
            fast = fast.next;
        }
        while(fast != null){
              fast = fast.next;
              slow = slow.next;  
        }
        return slow;

    }
}

0 赞同 0 条回复

Rona 普通 2023年7月15日下午6:32

快的先走k，然后再一起走。
时间复杂度：O(n)
空间复杂度：O(1)

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

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

0 赞同 0 条回复

hi 普通 2023年7月14日下午11:12

利用快慢指针解决问题

/**
 * 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* quicker = head;
        ListNode* latter = head;

    for(int i = 0; i < k; i++)
    {
        if(quicker == NULL) return NULL;
        quicker = quicker -> next;
    }

    while(quicker != NULL)
    {
        quicker = quicker -> next;
        latter = latter -> next;
    }
    return latter;
}
};

0 赞同 0 条回复

wowo 普通 2023年7月14日上午6:17

快指针先走K，慢指针从第一个开始，当慢指针到达链表尾部，快指针就在倒数第K个节点
O(n), O(1)

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        fast = head
        slow = head
        while k > 1:
            if fast.next is not None:
                fast = fast.next
                k = k-1
            else:
                break

        while fast.next is not None:
            fast = fast.next
            slow = slow.next

        return slow

0 赞同 0 条回复

洪小哲普通 2023年7月12日下午10:09

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* slow = head;
        ListNode* fast = head;
        for(int i=1; i<k; ++i)
        {
            if(fast->next != nullptr)
            {
                fast = fast->next;
            }
        }

        while(fast->next != nullptr)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};
快慢指针

0 赞同 0 条回复

始料未及普通 2023年7月12日下午8:36

“`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) {
ListNode slow=head;
ListNode quick=head;
int n=0;
while(n

0 赞同 0 条回复

星河普通 2023年7月12日下午2:42

/**
快节点先走k步后，慢节点再出发，
当快节点走到末尾最后一个节点时，慢节点指向的就是倒数第k个节点
*/
func getKthFromEnd(head *ListNode, k int) *ListNode {
if head nil {
return head
}
slow := head
fast := head

for ; k>0; k -- {
    if fast ==  nil {
        return fast
    } else {
        fast = fast.Next
    }
}
for fast != nil {
    slow = slow.Next 
    fast = fast.Next
}
return slow

}

0 赞同 0 条回复

望仔普通 2023年7月11日下午8:57

func getKthFromEnd(head *ListNode, k int) *ListNode {
    /*
       使用快慢指针，第一个指针先走k步，然后第二个指针才开始走
        等第一个走到底了，第二个就是走到了倒数第k个了
    */

    fast, slow := head, head

    for k > 0 {
        k--
        fast = fast.Next
    }

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

    return slow
}

0 赞同 0 条回复

我家旺仔普通 2023年7月11日上午10:47

打卡：
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode* l1 = head;
ListNode* l2 = head;
for(int i = 0; i < k;i++){
l1 = l1->next;
}
while(l1){
l1 = l1->next;
l2 = l2->next;
}
return l2;
}
};

0 赞同 0 条回复

momo 普通 2023年7月10日下午10:12

时间复杂度 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++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月10日下午7:43

”’C++
//打卡
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode *pre = head;
ListNode *tmp = head;
for(int i = 0;i < k;++i){
tmp = tmp->next;
}
while(tmp != nullptr){
pre = pre->next;
tmp = tmp->next;
}
return pre;
}
};
”’

0 赞同 0 条回复

NullPointerException 普通 2023年7月10日下午7:33

public ListNode getKthFromEnd(ListNode head, int k) {
//经典双指针
ListNode fast =head;
ListNode slow =head;
int a =1;
while(a<k)
{
a++;
fast=fast.next;
}
while(fast.next!=null)
{
fast=fast.next;
slow=slow.next;
}
return slow;
}

0 赞同 0 条回复

👾 普通 2023年7月10日下午4:03

“`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) {
//两个指针，第一个先走k，然后一起走，第一个到底，第二个返回的就是倒数的了
ListNode first = head;
ListNode laster = head;
for(int i=1;i<=k;i++) laster = laster.next; while(laster != null) { laster = laster.next; first = first.next; } return first; } }

0 赞同 0 条回复

jaho 普通 2023年7月10日下午2:07

打卡

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {

        ListNode pre = head, back = head;

        while(k !=0 ){
            back = back.next;
            k--;
        }
        while(back != null){
            pre = pre.next;
            back = back.next;
        }
        return pre;
    }
}

0 赞同 0 条回复

周小二普通 2023年7月10日上午2:04

class Solution {
    // public ListNode getKthFromEnd(ListNode head, int k) {
    //     //定义快慢节点
    //     ListNode fastNode = head, slowNode = head;
    //     for(int i = 0; fastNode!=null;i++) {
    //         //快节点先走k步
    //         if (i >= k) {
    //             slowNode = slowNode.next;
    //         }
    //         fastNode = fastNode.next;
    //     }
    //     return slowNode;
    // }

        public ListNode getKthFromEnd(ListNode head, int k) {
        //定义快慢节点
        ListNode fastNode = head, slowNode = head;
        //快节点先走k步
        for(int i = 0; i < k; i++) {
            fastNode = fastNode.next;
        }
        //快慢节点一起走
        while (fastNode != null) {
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }
        return slowNode;
    }
}

0 赞同 0 条回复

w 普通 2023年7月9日下午5:58

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;
        }
        //快慢指针一起走，走到快指针为null时，慢指针正好在倒数第k个节点
        while(fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        //返回节点
        return slow;
    }
}

0 赞同 0 条回复

神经蛙普通 2023年7月9日下午4:58

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

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        // 定义快慢指针
        ListNode quickNode = head;
        ListNode slowNode = head;

        // 快指针先走k步，然后快慢指针同时走，当快指针走到null时，慢指针与快指针相差k个节点，即倒数第k个节点
        for (int i = 0; i < k; ++i) {
            quickNode = quickNode.next;
        }

        // 快慢指针同时走
        while (quickNode != null) {
            slowNode = slowNode.next;
            quickNode = quickNode.next;
        }

        // 快指针指向null
        return slowNode;
    }
}

0 赞同 0 条回复

刹那芳间普通 2023年7月9日上午7:12

快慢指针

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 条回复

人生何处不青山普通 2023年7月8日下午11:28

估计也就我用TS写了

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function getKthFromEnd(head: ListNode | null, k: number): ListNode | null {
    let left = head, right = head;
    while (right && k--) {
        right = right.next;
    }
    while(right) {
        right = right.next;
        left = left.next;
    }
    return left;
};

0 赞同 0 条回复

ㅤ 普通 2023年7月8日下午11:04

/**
     * 剑指 Offer 22. 链表中倒数第k个节点
     * https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
     * 思路：通过创建双指针，指针front先走k，指针later不动，之后再front、later一块走，front到终点，那么later就是倒数第k个节点
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        // 特殊情况
        if (head == null) {
            return null;
        }
        ListNode front = head, later = head;
        // 快指针先走k步
        while (front != null && k-- > 0) {
            front = front.next;
        }
        // 快慢指针同时走，快指针走到终点，即慢指针就是倒数第k个节点
        while(front != null){
            front = front.next;
            later = later.next;
        }
        return later;
    }

0 赞同 0 条回复

mpweixin用户普通 2023年7月8日下午10:55

python代码

Definition for singly-linked list.

class ListNode(object):

def init(self, x):

self.val = x

self.next = None

class Solution(object):
def getKthFromEnd(self, head, k):
“””
:type head: ListNode
:type k: int
:rtype: ListNode
“””

    if head == None:
        return None

    former = head
    latter = head

    for i in range(k):
        former = former.next
        i +=1

    while former != None:
        if former.val == None:
            return latter
        former = former.next
        latter = latter.next

    return latter

0 赞同 0 条回复

Rico 普通 2023年7月8日下午8:59

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {

        if (head == nullptr) {
            return nullptr;
        }
        ListNode* fast = head;
        ListNode* slow = head;

        //让快指针先走k步
        for(int i=0;i<k;i++){
            if (fast == nullptr) {
                return nullptr;
            }
            fast = fast->next;
        }
        //最终慢指针指向倒数第k个节点
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }

        return slow;
    }
};

0 赞同 0 条回复

CKX 普通 2023年7月8日下午8:40

func getKthFromEnd(head *ListNode, k int) *ListNode {
    //双指针
    right := head
    left := head

    //右指针先于左指针k个节点
    for i := 0; i < k; i++ {
        right = right.Next
    }

    //右指针到达链表尾，则左指针所在节点为倒数第k个节点
    for right != nil {
        right = right.Next
        left = left.Next
    }

    return left

}

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

0 赞同 0 条回复

V2ero 普通 2023年7月8日下午8:30

代码如下

function getKthFromEnd(head: ListNode | null, k: number): ListNode | null {
    let slow = head;
    let fast = head;
    let count = 0;
    while(fast){
        if(count >= k){
            slow = slow.next
        }
        fast = fast.next
        count += 1
    }

    return slow
};

0 赞同 0 条回复

富城普通 2023年7月8日下午8:24

第一天第二题

/**
 * 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 nodeQuick=head;
        ListNode nodeSlow=head;

        if(head==null)
            return null;
        else
        {
            for(int i=0;i<=k-1;i++)
            {
                nodeQuick=nodeQuick.next;
            }
            while(nodeQuick!=null)
            {
                nodeSlow=nodeSlow.next;
                nodeQuick=nodeQuick.next;
            }


        }
        return nodeSlow;
    }

}

0 赞同 0 条回复

坏掉的世界永久会员 2023年7月8日下午8:09

代码如下：

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if(!head){
            return head;
        }
        auto dummy = new ListNode(-1);
        dummy -> next = head;

        int i = 0;
        auto p = dummy;
        while(i < k){
            p = p -> next;
            i++;
        }
        auto q = dummy;
        while(p){
            q = q -> next;
            p = p -> next;
        }
        return q;

    }
};

0 赞同 0 条回复

finalrgy 普通 2023年7月8日下午8:05

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getKthFromEnd(head *ListNode, k int) *ListNode {
    frontKthNode, Node := head, head
    // Node指向第k个节点
    for cnt := 0; cnt < k; cnt += 1 {
        if Node == nil {
            return nil
        }
        Node = Node.Next
    }
    // Node遍历到末尾
    for Node != nil {
        Node = Node.Next
        frontKthNode = frontKthNode.Next
    }

    return frontKthNode
}

用双指针，两个指针间隔k个节点，同时向前遍历后指针指向末尾，前指针刚好指向倒数第k个节点
时间复杂度O(N)，空间复杂度O(1)

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月8日下午7:57

代码如下

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 条回复

#00456B 普通 2023年7月8日下午7:29

快慢指针，先让快指针走k次，然后判断fast是不是空，若不是的话就slow和fast一起走一次

/**
 * 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* slow = head;
        ListNode* fast = head;
        while(k--){
            fast=fast->next;
        }
        while(fast != NULL){
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

0 赞同 0 条回复

普通 2023年7月8日下午7:21

c++ 代码，快慢指针法
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode* pre=head;
ListNode* follow=head;
for(int i=0;i<k;i++)
pre=pre->next;
while(pre)
{
pre=pre->next;
follow=follow->next;
}
return follow;
}
};

0 赞同 0 条回复

3A87 普通 2023年7月8日下午5: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) {
        if(head==nullptr)
            return nullptr;
        ListNode* fast=head;
        ListNode* slow=head;
        for(int i=1;i<=k;i++) //快指针先向前移动k步
        {
            if(fast==nullptr) return nullptr;
            fast=fast->next;
        }
        while(fast!=nullptr)  //慢指针向前移动n-k步
        {
            fast=fast->next;
            slow=slow->next;
        }
        return slow;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月8日下午5:34

双指针打卡

/**
 * 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* ptr1,*ptr2;
    ptr1=head;
    ptr2=head;
    for(int i=0;i<k-1;i++){

        ptr1=ptr1->next;
    }
    while(ptr1->next!=NULL){
        ptr1=ptr1->next;
        ptr2=ptr2->next;
    }
    return ptr2;
    }
};

0 赞同 0 条回复

Ad. 普通 2023年7月8日下午5:29

方法是双指针中的快慢指针。具体如下：
1. 先让快指针往前走k步。
2. 再让快慢指针同时走，直至快指针指向为null
3. 此时慢指针就会到达倒数第k个节点，返回即可

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

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

0 赞同 0 条回复

Edenms-u 普通 2023年7月8日下午5:20

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


struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    if(head == NULL)
        return head;
    struct ListNode *ahead, *bhead;
    ahead = bhead = head;
    for(int i = 1; inext;
    }
    while(bhead->next != NULL){
        ahead = ahead->next;
        bhead = bhead->next;
    }
    return ahead;
}

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

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月8日下午4:40

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null || head.next == null) return head;
        ListNode p = head;
        ListNode result = head;
        for(int i = 1; p.next != null; i++){
            p = p.next;
            if(k <= i){
                result = result.next;
            }
        }
        return result;
    }
}

时间复杂度O(n)

0 赞同 0 条回复

小季同学普通 2023年7月8日下午4:23

快慢指针，当fast指向null的时候，slow指向的位置就是倒数第k个节点，fast和slow相差k个节点，才能保证fast指向nullslow指向倒数第k个节点

function getKthFromEnd(head: ListNode | null, k: number): ListNode | null {
    // 边界判断
    if(!head || !head.next) return head
    // 快慢指针
    let slow: ListNode | null = head
    let fast: ListNode | null = head
    // fast赋值
    for(let i = 0; i < k; i++) {
        fast = fast.next
    }
    while(fast) {
        slow = slow.next
        fast = fast.next
    }
    return slow

};

0 赞同 0 条回复

offer收割机普通 2023年7月8日下午3:18

打卡剑指 Offer 22. 链表中倒数第k个节点

双指针法

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

0 赞同 0 条回复

mpweixin用户普通 2023年7月8日下午2:54

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //给定一个链表: 1->2->3->4->5, 和 k = 2.
        //返回链表 4->5.
        ListNode slow = new ListNode(-1);
        slow.next = head;
        ListNode fast = new ListNode(-1);
        fast.next = head;
        while (k>0) {
            fast = fast.next;
            k--;
        }
        while (fast.next!=null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.next;
    }
}

0 赞同 0 条回复

ppopp 普通 2023年7月8日下午1:11

/**
* 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(k){
fast = fast->next;
k–;
}
while(fast->next != nullptr){
fast = fast -> next;
slow = slow -> next;
}
return slow;
}
};

0 赞同 0 条回复

枫梓。普通 2023年7月8日下午12:53

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* first=head;
        ListNode* dummy = new ListNode(0, head);
        ListNode* second = dummy;
        for(int i = 0; i < k; i++){
            first = first->next;
        }
        while(first){
            first = first->next;
            second = second->next;
        }
        return second->next;
    }
};

获得倒数第n个结点，双指针。O(n)

0 赞同 0 条回复

艺普通 2023年7月8日下午12:44

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

struct ListNode* getKthFromEnd(struct ListNode* head, int k){
struct ListNode *fast=head;
struct ListNode *slow=head;
if(head= = NULL) return NULL;
int i;
for(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 条回复

H、普通 2023年7月8日下午12:27

双指针，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 head;
        }

        //快指针
        ListNode fastK = head;

        //因为题目是从1开始计数，不从0；代码中转换成从0计数。
        int kForFast = k - 1;

        //快指针先走K个节点
        while (fastK != null && kForFast > 0){
            fastK = fastK.next;
            kForFast--;
        }

        //如果k比链表节点数量多,此题无解
        if(kForFast > 0){
            return  null;
        }

        //如果这个链表刚好有K个节点，则返回当前链接
        if(fastK.next == null){
            return head;
        }

        //慢指针
        ListNode slow = head;

        //当快指针走到最后了，慢指针所在位置，就是倒数第K个节点的位置
        while (fastK.next != null){
            fastK = fastK.next;
            slow = slow.next;
        }

        return slow;


    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月8日下午12:23

java
代码
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 p1 = head;//快指针
ListNode p2 = head;//慢指针

for(int i = 0; i < k; i++){
if(p1 null){// k大于链表长度
return null;}
p1= p1.next;
}

while(p1 != null){//k<= 链表长度
p1 = p1.next;
p2 = p2.nextl
}
return p2;
}
}

0 赞同 0 条回复

Fighting boy😀 普通 2023年7月8日下午12:20

//C++双指针实现
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
if (head nullptr) {

        return nullptr;
    }

    ListNode* fast = head;  //快指针
    ListNode* slow = head;  //慢指针
    //第一步，快指针先走K
    for (int i = 0; i < k; i++) {
        if(fast == nullptr) {
            return nullptr;
        }
        fast = fast->next;
    }
    //第二步，快指针、慢指针同步走，直到快指针的next指向nullptr，说明快指针已指向最后一个元素，此时慢指针刚好指向倒数第K个元素
    while(fast != nullptr) {
        fast = fast->next;
        slow = slow->next;
    }
return slow;
}

};

0 赞同 0 条回复

爱吃胡萝卜🥕的兔子🐰 普通 2023年7月8日下午12:14

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteNode(head *ListNode, val int) *ListNode {
    dummy := &ListNode{
        Next: head,
    }
    cur := dummy.Next
    pre := dummy
    for cur != nil{
        if cur.Val == val{
            pre.Next = cur.Next
            break
        }
        pre = cur
        cur = cur.Next
    }
    return dummy.Next
}

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

0 赞同 0 条回复

片言莫语普通 2023年7月8日下午12:10

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head==null){
            return null;
        }   //判断空指针异常
        ListNode fast = head;   //设置快慢指针
        ListNode slow = fast;
        for(int i = 0;i < k;i++){   //快指针先走k步
            fast = fast.next;  
        }
        while(fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;    //返回慢指针，输出的慢指针到慢指针后面的结点
    }
}

0 赞同 0 条回复

Mooby 普通 2023年7月8日上午11:32

第一天

/**
 * 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 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 赞同 0 条回复

远行客普通 2023年7月8日上午11:12

class ListNode:
    def __int__(self, x):
        self.val = x
        self.next = None

    class Solution:
        def getKthFromEnd(self, head, k):
            # 使用快慢双指针的方法
            # 初始化， 前后指针都指向头节点
            former = head
            latter = head

            # 前指针先走k步， 这样前后指针就间距k个节点
            for _ in range(k):
                if not former:
                    return
                former = former.next

            # 前后指针共同移动， 直到前指针走过链表的尾节点
            while former:
                former = former.next
                latter = latter.next

            return latter

"""
时间复杂度：O(N), N为链表长度
空间复杂度：O(1)
"""

0 赞同 0 条回复

mpweixin用户普通 2023年7月8日上午10:57

java
public Node deleteNodek(Node head,int k ){
Node p,q;
p=head;
q=head;
for (int i=0;i<k;i++){
p=p.next;
}
while (p.next!=null){
p=p.next;
q=q.next;
}
return q;
}
时间复杂度O(n)
空间复杂度O(1)

0 赞同 0 条回复

波雅汉库克普通 2023年7月8日上午3:46

/**
 * 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* start = head;
        for(int i=0; i<k; i++){
            start = start->next;
        }
        while(start!=nullptr){
            start = start->next;
            head = head->next;
        }
        return head;
    }
};

时间复杂度： O(n)
Space: O(1)

0 赞同 0 条回复

KCOcean 普通 2023年7月8日上午1:04

代码

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

    }

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月8日上午12:59

Day1：下面是代码
#双指针

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

0 赞同 0 条回复

旺旺旺普通 2023年7月8日上午12:11

以下是代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if head==None:
            return None

        fast=head
        slow=head
        i=0
        while i<k:
            if fast==None:
                return None
            fast=fast.next
            i+=1

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

0 赞同 0 条回复

是非之欢普通 2023年7月7日下午11:46

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

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

0 赞同 0 条回复

醒醒醒醒普通 2023年7月7日下午11:25

/**
 * 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 == nullptr){
            return nullptr;
        }

        ListNode* p = head;
        ListNode* q = head;
        for (int i = 0; i < k; i++){
            if (p == nullptr){
                return nullptr;
            }
            p = p->next;
        }

        while (p != nullptr){
            p = p->next;
            q = q->next;
        }

        return q;

    }
};

1.使用快慢双指针，快指针先走k步，之后快慢指针一起走，快指针为空时，返回慢指针的值
2.O（n），O（1）

0 赞同 0 条回复

Luminous 普通 2023年7月7日下午11:24

/**
 * 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 vHead=new ListNode();
        vHead.next=head;
        ListNode fast=vHead;
        ListNode slow=vHead;
        for(int i=0;i<k;i++){
            //遍历到第k个节点
            fast=fast.next;
        }
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
}

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

0 赞同 0 条回复

阿尚普通 2023年7月7日下午11:06

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

    ListNode fast = head;
    ListNode slow = head;

//快指针先移动k步
while(k > 0){
fast = fast.next;
k–;
}
//快慢指针一起移动
while(fast != null){
fast = fast.next;
slow = slow.next;
}

    return slow;
}

}

0 赞同 0 条回复

mpweixin用户普通 2023年7月7日下午10: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) {
        // 使用快慢指针
        // 快指针先跑K步，之后再快慢指针一起跑
        // 当快指针为空时，慢指针到达倒数第K个
        // 需要判空
        if(head == null || k<0) return null;
        ListNode slow=head, fast=head;
        while(k>0){
            if(fast==null) return null;
            fast = fast.next;
            k--;
        }
        while(fast!=null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

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

0 赞同 0 条回复

momo 普通 2023年7月7日下午10:47

struct ListNode* getKthFromEnd(struct ListNode* head, int k){

    // 定义两个指针，都指向head

    struct ListNode * index1 = head;

    struct ListNode * index2 = head;



    // index2领先index1，k-1个位置

    int count = k-1;

    while(count>0 && index2){

        index2 = index2->next;

        count--;

    }



    // index1、index2遍历整个链表

    while(index2->next){

        index2 = index2->next;

        index1 = index1->next;

    }

    return index1;

}

0 赞同 0 条回复

mpweixin用户普通 2023年7月7日下午10:40

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

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        List<ListNode> list=new ArrayList<>();
        ListNode temp=head;
        while(temp!=null){
            list.add(temp);
            temp=temp.next;
        }
        int size=list.size();
        return list.get(size-k);
    }
}

0 赞同 0 条回复

@ 李小二普通 2023年7月7日下午10:39

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

    int count = 0;

    while(fast != null){
        if(count >= k){
            slow = slow.next;
        }
        fast = fast.next;
        count++;
    }

    if(count < k) {
        return null;//处理链表长度不足k的情况
    }


    return slow;


}

}

0 赞同 0 条回复

朱志刚普通 2023年7月7日下午10:38

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

}
执行用时：
4 ms

0 赞同 0 条回复

Terence💧 普通 2023年7月7日下午10:30

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

    fast, slow := head, head

    for i := 1; i <= k; i++ {
        fast = fast.Next
    } 

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

时间复杂度On

0 赞同 0 条回复

新禾普通 2023年7月7日下午10:00

快慢指针，让快指针先走k步，慢指针在head，然后快慢一起走，那么快指针走到null时，慢指针就是倒数的第k个
比如 1 2 3 4 5，k等于2，刚开始快慢都在1.，然后快指针先走两步到3，两个一起走，当快指针走到5，慢指针走到3，快指针继续走到null，慢指针走到4，4就是所要的位置
时间复杂度On
空间复杂度O1
public ListNode getLastKListNode(ListNode head, int k) {
if (head null) return head;
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;
}
}

0 赞同 0 条回复

白鹿普通 2023年7月7日下午9:51

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if (!head) return nullptr;
     ListNode *fast_p = head;
    ListNode *slow_p = head;

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

    while (fast_p != nullptr) {
        fast_p = fast_p->next;
        slow_p = slow_p->next;
    }

    return slow_p;
}
};

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

0 赞同 0 条回复

北辰普通 2023年7月7日下午9:21

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

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

0 赞同 0 条回复

ONE PIECE 普通 2023年7月7日下午9:06

/**
 * 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 = new ListNode(0);
        // pre.next=head;
        ListNode slow=head;
        ListNode fast=head;
        while(k>1){
            fast=fast.next;
            k--;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

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

0 赞同 0 条回复

桎梏普通 2023年7月7日下午8:55

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

public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
while(k > 1) {
fast = fast.next;
k–-;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
return slow;

}

0 赞同 0 条回复

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

共以下 74 个回答

Definition for singly-linked list.

class ListNode(object):

def init(self, x):

self.val = x

self.next = None

打卡剑指 Offer 22. 链表中倒数第k个节点

双指针法

# 回答此问题取消回复

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

共以下 74 个回答

Definition for singly-linked list.

class ListNode(object):

def init(self, x):

self.val = x

self.next = None

打卡剑指 Offer 22. 链表中倒数第k个节点

双指针法

# 回答此问题 取消回复

# 回答此问题取消回复