吃碗草莓豆沙普通 2024年12月9日下午2:04

class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
//异常情况判断
if(head nullptr){
return head;
}
//定义两个指针，一个快一个慢
ListNode *fastptr = head;
ListNode *slowptr = head;
//将快指针指向正向的第cnt个节点
for(int i = 0; i < cnt; i++)
{
if(fastptr nullptr){
return head;
}
else{
fastptr = fastptr->next;
}
}
//快指针和慢指针开始同步移动，直到快指针指向null，此时慢指针刚好指向倒数第cnt个节点
while(fastptr != nullptr)
{
fastptr = fastptr->next;
slowptr = slowptr->next;
}

return slowptr;

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

0 赞同 0 条回复

宇晴普通 2024年11月30日下午11:06

最简单直接的方法即为顺序查找，假设当前链表的长度为 n，则我们知道链表的倒数第 cnt 个节点即为正数第 n−cnt 个节点，此时我们只需要顺序遍历到链表的第 n−cnt 个节点即为倒数第 cnt 个节点。

我们首先求出链表的长度 n，然后顺序遍历到链表的第 n−cnt 个节点返回即可。

var trainingPlan = function(head, cnt) {
    let node = head, n = 0;
    while (node) {
        node = node.next;
        n++;
    }
    node = head;
    for (let i = 0; i < n - cnt; i++) {
        node = node.next;
    }
    return node;
};

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日上午1:48

/**
解题思路：
思路一：
反转链表在正序取，最坏情况下，需要遍历两次，时间复杂度O(N)
思路二：
取两个指针left和right间距cnt-1遍历，right抵达末尾时，left正好在倒数第cnt个位置，只遍历一次，时间复杂度O(N)
 */
class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {

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

        ListNode dummy = new ListNode(-1, head);

        ListNode right = dummy;

        int step = cnt - 1;
        for (int i = 0; i < step; i++){
            right = right.next;
        }

        ListNode left = dummy;
        while (right.next != null){
            right = right.next;
            left = left.next;
        }

        return left;

    }
}

0 赞同 0 条回复

泽阳普通 2024年11月28日下午2:15

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

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode head2 = head;
        for(int i = 0; i < cnt; i++) {
            head = head.next;
        }

        while(head != null) {
            head = head.next;
            head2 = head2.next;
        }

        return head2;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年11月28日下午1:02

快慢指针

class Solution:
    def trainingPlan(self, head: Optional[ListNode], cnt: int) -> Optional[ListNode]:
        fast = head
        slow = head
        for int in range(cnt):
            fast = fast.next
        while fast:
            fast = fast.next
            slow = slow.next
        return slow

0 赞同 0 条回复

為愛而生普通 2024年11月26日下午11:56

//时间0ms 内存40mb
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
ListNode p = head;
ListNode c = head;
int length = 0;
int cur = 0;
while (p != null) {
length++;
p = p.next;
}
cur = length – cnt;
for (int i = 1; i <= cur; i++) {
c = c.next;
}
return c;

}

0 赞同 0 条回复

Lil Lee_ 普通 2024年11月26日下午9:25

//单指针遍历法
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        if(head == null) return head;
        //统计链表长度
        int len = 0;
        ListNode cur1 = head;
        while(cur1 != null){
           len++;
           cur1 = cur1.next; 
        }
        //循环查找倒数第n个节点
        ListNode cur2 = head;
        while(len > cnt){
            len--;
            cur2 = cur2.next;

        }
        return cur2;
    }
}

//双指针
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
if(head null) return head;
ListNode former = head, latter = head;
while(cnt > 0){
cnt–;
former = former.next;
}

    while(former != null){
        former = former.next;
        latter = latter.next;
    }
    return latter;
}

}

0 赞同 0 条回复

树懒在橘子洲数星星普通 2024年11月25日下午6:10

“`python
class Solution(object):
def trainingPlan(self, head, cnt):
//初始化
l=head
r=head
//r指针指向第k个节点
while cnt>0 and r:
r=r.next
cnt-=1
//r不为空进行后移遍历
while r:
r=r.next
l=l.next
return l
时间复杂度：O(N) N为链表长度
空间复杂度：O(1) r，l为常数项额外开销

0 赞同 0 条回复

无言永久会员 2024年11月23日下午4:47

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* trainingPlan(ListNode* head, int cnt) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && cnt > 0) {
            fast = fast->next;
            cnt--;
        }
        while(fast) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};
时间复杂度: O(n)
空间复杂度: O(1)

0 赞同 0 条回复

借来的猫普通 2024年11月23日上午10:37

class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
ListNode cur=head;
ListNode pre=head;
for(int i=0;i<k;i++){
if(cur!=null)cur=cur.next;
}
while(cur!=null){
cur=cur.next;
pre=pre.next;
}
return pre;
}
}
时间复杂O(n)、空间复杂度O(1)

0 赞同 0 条回复

捕风永久会员 2024年11月22日下午8:31

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int kthToLast(ListNode head, int k) {
        // 首先判断特殊情况：链表是否为空
        if(head == null){
            return -1;
        }

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

        // 让快指针先走k步
        for(int i = 0; i < k; i++){
            // 如果fast指针出界（意味着链表长度小于k），返回-1
            if(fast == null){
                return -1;
            }
            // 否则fast继续往下走
            fast = fast.next;

        }

        // 慢指针和快指针一起走，直到快指针到达链表末尾null
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }

        // 返回慢指针的值（int型），即倒数第k个指针的位置
        return slow.val;

    }
}

0 赞同 0 条回复

岱永久会员 2024年11月22日下午4:44

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        //找出一共几个
        ListNode p = head;
        int l = 0;
        while(p != null){
            l++;
            p=p.next;
        }
        p=head;
        for(int i = 1; i < l-cnt+1; i++  )//倒数cnt，正数 l-cnt+1
        {
            p=p.next;
        }
        return p;
    }
}

0 赞同 0 条回复

yelinliner 普通 2024年11月21日下午11:32

第一种遍历2次

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        // 题目中以提示head、cnt的范围 所以不必做非空判断
        // 1、临界情况
        if (cnt == 1 && head.next == null) {
            // 只有一个节点
            return head;
        }
        // 2.两次遍历
        // 遍历取得链表长度
        int len = 0;
        ListNode temp = head;
        while (temp != null) {
            len++;
            temp = temp.next;
        }
        // 遍历倒数cnt个节点,即正数len-cnt+1步
        ListNode cur = head;
        for(;len>cnt;len--){
            cur=cur.next;
        } 
        return cur;
    }
}

第二种只遍历一次链表

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        // 题目中以提示head、cnt的范围 所以不必做非空判断
        // 1、临界情况
        if (cnt == 1 && head.next == null) {
            // 只有一个节点
            return head;
        }
        // 2.双指针
        ListNode fast = head;
        for (int i = 0; i < cnt; i++) {
            // 快指针先走cnt步
            fast = fast.next;
        }

        ListNode slow = head;
        while (fast != null) {
            // 快、慢指针同时走，其差值始终为cnt
            // 所以快指针走完的时候 慢指针刚好就在倒数cnt的位置
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

0 赞同 1 条回复

yelinliner 普通 @ yelinliner 2024年11月21日下午11:35

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

登录以回复

biangbb 普通 2024年11月21日下午10:25

“`java 1.长度2.再次循环len-cnt
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
int len=0;
ListNode p=head;
while(p!=null){
len++;
p=p.next;
}
p=head;
while(len!=cnt){
len–;
p=p.next;
}
return p;
}
}
“`

0 赞同 0 条回复

打豆豆啊打豆豆普通 2024年11月21日下午10:24

1、异常处理：若头指针为空，则返回空指针；
2、定义两个指针，快指针和慢指针，都指向头节点，然后使用for循环，将快指针指向正向第k个节点，for循环中若发现指针为空，则返回头节点
3、进入循环，判断快指针是否为空，若快指针不为空，则快指针与慢指针都向前移动一个节点，直至快指针为空，此时慢指针就指向倒数第K个节点；

“`C++
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
if(head == nullptr) return nullptr;

    ListNode *slowPtr = head;
    ListNode *fastPtr = head;
    for(int i=0;i<cnt;++i)
    {
        if(fastPtr == nullptr) return head;
        else fastPtr = fastPtr->next;
    }
    while(fastPtr != nullptr)
    {
        slowPtr = slowPtr->next;
        fastPtr = fastPtr->next;
    }

    return slowPtr;

}

};

“`

0 赞同 0 条回复

爱姆露普通 2024年11月21日下午10:24

class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
if(cnt 0 )
{
return head;
}

    ListNode * fast = head;
    ListNode * slow = head;
    for(int i = 0; i<cnt;i++)
    {
        if(fast == nullptr)
        {
            return nullptr;
        }
        fast = fast->next;
    }

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

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

0 赞同 0 条回复

Poetry and distance 永久会员 2024年11月21日下午9:01

思路：首先快指针先走k步，慢指针接着和快指针同步走，直到快指针为空指针为止，注意指针为指针情况，其次，由于链表的长度小于k的生活，快指针需要做判断为空处理，避免空指针异常
代码：
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode kthToLast(ListNode head, int k) {
        if(head==null){
            return null;
        }
        ListNode slow=head,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;
    }
}
时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

橙子陈爱吃橙子普通 2024年11月21日下午7:37

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        if (null == head) return null;
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < cnt; i++) {
            if (fast == null) return null;
            fast = fast.next;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

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

0 赞同 0 条回复

桃桃摇摇奶昔° 普通 2024年11月21日下午2:18

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

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode f = head;
        ListNode s = head;
        // 让快指针到第ctn个节点
        for (int i = 0; i < cnt; i++) {
            f = f.next;
        }
        while (f != null) {
            f = f.next;
            s = s.next;
        }
        return s;
    }
}

0 赞同 0 条回复

zing 普通 2024年11月21日下午12:01

设置虚拟头结点

class Solution:
    def trainingPlan(self, head: Optional[ListNode], cnt: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)

        fast = slow = dummy.next
        for i in range(cnt-1):
            fast = fast.next

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

0 赞同 0 条回复

Renasc 普通 2024年11月21日上午10:40

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

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        if (head == null && head.next == null) {
            return head;
        }

        // 设置虚拟头结点
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // 设置快慢指针
        ListNode fast = dummy.next;
        ListNode slow = dummy.next;

        // 先让快指针走cnt步
        for (int i=0; i<cnt; i++) {
            fast = fast.next;
        }

        // 让快慢指针一起走，等快指针结束，慢指针就到了倒数第cnt个位置
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年11月21日上午10:34

解题思路：

这道题可以巧妙地使用快慢指针来解决。解题的核心思想是让一个快指针先走cnt步，然后快慢指针再同时前进。这样当快指针到达链表末尾时，慢指针正好位于倒数第cnt个节点。这是因为快慢指针之间始终保持着cnt个节点的距离，当快指针走到末尾，慢指针自然就处于倒数第cnt个位置。

具体来说，我们首先让快指针从头节点开始向前移动cnt步。这个过程中需要注意检查快指针是否为空，如果为空说明链表长度小于cnt，此时应该返回空。当快指针移动完cnt步后，我们开始同时移动快慢指针，直到快指针到达链表末尾。此时慢指针指向的就是我们要找的倒数第cnt个节点。

时空复杂度：

时间复杂度：O(n)，其中n为链表的长度。虽然使用了快慢指针，但实际上只需要遍历一次链表就能得到结果。空间复杂度：O(1)，只使用了两个指针变量，所需额外空间固定。

代码实现：

“`C++
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
// 处理空链表的边界情况
if(head == nullptr) return nullptr;
ListNode* fast = head;
ListNode* slow = head;

    // 让快指针先走cnt步
    for(int i = 0;i<cnt;i++){
        if(fast == nullptr){
            return nullptr;  // 链表长度小于cnt的情况
        }
        fast = fast->next;
    }

    // 快慢指针同时移动，直到快指针到达末尾
    while(fast != nullptr){
        fast = fast->next;
        slow = slow->next;
    }
    // 此时slow指向倒数第cnt个节点
    return slow;
}

};

“`

0 赞同 0 条回复

Rad 普通 2024年11月21日上午10:21

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
if(head null){return null;}
ListNode first = head;
ListNode second = head;
for(int i=0;i<cnt;i++){
first = first.next;}
while(first != null){
first = first.next;
second = second.next;
}
return second;

}
时间复杂度On
空间复杂度O1

0 赞同 0 条回复

Tom Yuan 普通 2024年11月21日上午10:06

快慢指针都从头开始一个提前走k步当先走的那个到达结尾后的null 后走的就是结果

class Solution:
    def trainingPlan(self, head: Optional[ListNode], cnt: int) -> Optional[ListNode]:
        # the first pointer is where it lands at cnt
        # when the second pointer reaches the end
        first = head
        second = head
        for i in range(cnt):
            if second == None:
                # the list is shorter than cnt
                return None
            second = second.next

        while second != None:
            first = first.next
            second = second.next

        return first

有个注意的点是先开始走的时候的判断条件如果先走的点本身已经变成null了那么就可以停下输出null了而不是判断他的下一个
判断下一个是null的话可能会出现越过了最后一个点的情况。

time: O(n) 前半段O(k) 后半段O(n – k)
space: O(1) 两个指针

0 赞同 0 条回复

mpweixin用户普通 2024年11月21日上午9:23

打卡

“`c++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
ListNode* fast = head;
ListNode* slow = head;
if(head == nullptr){
return nullptr;
}
while(cnt–){
fast = fast->next;
}
while(fast!=nullptr){
fast = fast->next;
slow = slow->next;
}
return slow;

};

“`

0 赞同 0 条回复

jaron 普通 2024年11月21日上午9:10

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

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode temp = head;
        for (int i = 0; i < cnt; i++) {
            if (temp == null) {
                return null;
            }
            temp = temp.next;
        }
        while (temp != null) {
            temp = temp.next;
            head = head.next;
        }
        return head;
    }
}

0 赞同 0 条回复

土豆哥普通 2024年11月21日上午2:33

“`java
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
ListNode former = head, latter = head;
for(int i=0;iwhile(former!=null) { former = former.next; latter = latter.next; } return latter; }

}

0 赞同 0 条回复

Pendulumpal 普通 2024年11月21日上午12:07

遍历链表得到链表长度，以便得到所要找点的编号

“`c++
ListNode* trainingPlan(ListNode* head, int cnt) {
ListNode* p=head;
int len=0;
while(p){
len++;
p=p->next;
}
int id=len-cnt;
int cur=0;
p=head;
while(p){
cur++;
p=p->next;
if(cur==id)return p;
}
return head;
}
“`

0 赞同 0 条回复

咕普通 2024年11月20日下午11:38

class Solution:
    def trainingPlan(self, head: Optional[ListNode], cnt: int) -> Optional[ListNode]:
        former, latter = head, head
        for _ in range(cnt):
            former = former.next
        while former:
            former, latter = former.next, latter.next
        return latter

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

0 赞同 0 条回复

ㅤ牛马学编程普通 2024年11月20日下午11:14

“`java
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
// 定义变量n
int n = 0;
ListNode node = null;
for (node = head; node != null; node = node.next) {
// 遍历链表统计链表长度
n++;
}

    for (node = head; n > cnt; n--) {
        node = node.next;
    }
    return node;
}

}

0 赞同 0 条回复

Firefly 普通 2024年11月20日下午11:09

“`c++
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
auto p = head, q = head;
while (q != nullptr && cnt– > 0) {
q = q->next;
}

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

    return p;
}

};
时间复杂度O(N)，空间复杂度O(1)

0 赞同 0 条回复

遇事不决睡大觉普通 2024年11月20日下午11:05

“`java
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
ListNode former = head, latter = head;
for(int i = 0; i < cnt; i++)//一直找到要返回的前一个节点 former = former.next; while(former != null) { former = former.next; latter = latter.next; } return latter; } }

0 赞同 0 条回复

陆狗陆狗普通 2024年11月20日下午10:45

题解

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode slow=head;
        ListNode quick=head;
        for(int i=0;i<cnt;i++){
            quick=quick.next;
        }
        // 【错误1】
        while(quick!=null){
            slow=slow.next;
            quick=quick.next;
        }
        return slow;
    }
}

错误点1 没有考虑到倒数第1个就是最末端那个。

0 赞同 0 条回复

时光烙印普通 2024年11月20日下午10:38

双指针：
class Solution:
def trainingPlan(self, head: Optional[ListNode], cnt: int) -> Optional[ListNode]:
former, latter = head, head
for _ in range(cnt):
former = former.next
while former:
former, latter = former.next, latter.next
return latter

0 赞同 0 条回复

lQl 永久会员 2024年11月20日下午10:34

双指针:

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode front = head;
        ListNode back = head;
        while(cnt-->0){
            front = front.next;
        }
        while(front!=null){
            front=front.next;
            back=back.next;
        }
        return back;
    }
}

0 赞同 0 条回复

🌟 普通 2024年11月20日下午10:30

时间O(n) 空间O(n)
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
vector<ListNode> v;
int len=0;
ListNode cur=head;
while(cur!=nullptr){
++len;
v.push_back(cur);
cur=cur->next;
}
return v[len-cnt];
}
};

0 赞同 0 条回复

张君雅小妹妹普通 2024年11月20日下午10:29

快指针最远可以为null

    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode fast = head;
        ListNode slow = head;
        int i = 0;
        while (i < cnt){
            fast = fast.next;
            i++;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

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

0 赞同 0 条回复

晓宇普通 2024年11月20日下午10:18

注意块指针判空，安全意识！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode trainingPlan(ListNode* head, int cnt) {
if(head nullptr) return nullptr;
ListNode *fast = head, *slow = head;

    while(--cnt){
        if(fast == nullptr) return nullptr;
        fast = fast->next; 
    }

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

};

0 赞同 0 条回复

C。普通 2024年11月20日下午10:15

思路

先判断头节点是否是空
if(head null){
return null;
}
再定义快慢指针指向头节点
ListNode fast = head, slow = head;
再用for循环让fast快指针先走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;
}
代码
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
if(head null){
return null;
}
ListNode fast = head, slow = head;
for(int i=0; i<cnt; i++){
if(fastnull){
return null;
}
fast = fast.next;
}
while(fast!=null){
fast =fast.next;
slow = slow.next;
}
return slow;
}
}
时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

越努力越幸运普通 2024年11月20日下午10:10

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode trainingPlan(ListNode* head, int cnt) {
if(nullptr head)
{
return nullptr;
}
ListNode* fast = head;
ListNode* slow = head;
for(int i = 0; i < cnt; i++)
{
if(nullptr fast)
{
return nullptr;
}
fast = fast->next;
}
while(nullptr != fast)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
//时间复杂度：O(n)
//空间复杂度：O(1)

0 赞同 0 条回复

生活在经验里普通 2024年11月20日下午9:40

go代码实现
func trainingPlan(head *ListNode, cnt int) *ListNode {
fast := head
slow := head
for i := 0; i < cnt; i++ {
fast = fast.Next
}
for fast != nil {
fast = fast.Next
slow = slow.Next
}
return slow
}

0 赞同 0 条回复

. 普通 2024年11月20日下午9:14

时间O(n),空间O(1)
两个指针，前一个和后一个间隔cnt-1，一起向前挪动。
可能我不太熟悉leetcode，看到输出只有一个数，还特意new了一个只包含一个的，结果没通过（）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
ListNode front = head;
ListNode back = head;
for(int i = 1; i < cnt; i++){
front = front.next;
}
while(front.next != null){
front = front.next;
back = back.next;
}

    return back;
}

}

0 赞同 0 条回复

Jerry 普通 2024年11月20日下午9:02

class Solution {
public:
    ListNode* trainingPlan(ListNode* head, int cnt) {
        ListNode* fast = head;
        ListNode* slow = head;
        for(int i = 0; i < cnt && fast; i++){
            fast = fast->next;
        }
        while(fast && slow){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

时间o(n)
空间o(1)

0 赞同 0 条回复

momo 普通 2024年11月20日下午8:57

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

class Solution:
def trainingPlan(self, head: Optional[ListNode], cnt: int) -> Optional[ListNode]:
slow = head
fast = head
for i in range(0,cnt):
fast = fast.next
while(fast):
fast = fast.next
slow = slow.next
return slow
时间复杂度O（n）空间复杂度O（1）双指针方法

0 赞同 0 条回复

Carry on 普通 2024年11月20日下午8:55

“` java

class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
if (head null || cnt <= 0) {
return null; // 无效输入，返回 null
}

    // 快慢指针初始化
    ListNode fast = head;
    ListNode slow = head;

    // 快指针先走 cnt 步
    for (int i = 0; i < cnt; i++) {
        if (fast == null) {
            return null; // cnt 大于链表长度
        }
        fast = fast.next;
    }

    // 快慢指针同时移动，直到快指针到达末尾
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    // 慢指针指向的就是倒数第 cnt 个节点
    return slow;
}

}

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

0 赞同 0 条回复

mpweixin用户普通 2024年11月20日下午8:51

class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
ListNode* fast = head;
for(int i=cnt; i>0; i–){
if(fast){
fast=fast->next;
}
else{
return NULL;
}
}
ListNode* result = head;
while(fast){
fast = fast->next;
result = result->next;
}
return result;
}
};
思路：快慢指针，先让一个指针移动k，之后两个指针用相同的速度移动，先移动的指针遍历完成时另一个就是所求位置。
时间复杂度O(n)，空间复杂度O(1)

0 赞同 0 条回复

Xiang. 永久会员 2024年11月20日下午8:51

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
if(headnull) return null;
ListNode fast=head;
ListNode slow=head;
while(cnt>1){
if(fastnull) return null;
fast=fast.next;
cnt–;
}
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}
时间复杂度O(n)
空间复杂度O(1)

0 赞同 0 条回复

hjx 普通 2024年11月20日下午8:48

class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
ListNode slow=head,fast=head;
for(int i=1;i<cnt;i++){
fast=fast.next;
}
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}
时间 O(N),空间O(1)

0 赞同 0 条回复

mpweixin用户普通 2024年11月20日下午8:40

a.思路解析
1.定义两个节点fast、slow
2.先让fast走k步，slow原地待命
3.接下来fast走到最后一个空节点时会继续走n-k步，而slow也会走n-k步，此时slow的位置就为倒数第k个节点。
b.代码

class Solution {
public:
    ListNode* trainingPlan(ListNode* head, int cnt) {
        if(head == nullptr) return nullptr;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast!=nullptr && cnt--)
        {
            fast = fast->next;
        }
        while(fast != nullptr)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

c.时间复杂度:o(n),n为链表的长度；空间复杂度为0(1),额外使用了常数级的内存空间。

0 赞同 0 条回复

月下足迹普通 2024年11月20日下午8:38

设置快慢指针，让快指针先走k步，然后while循环，直到快指针到链表尾部，此时慢指针指向的就是倒数第k个节点

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
ListNode fast = head;
ListNode slow = head;

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

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

    return slow;
}

}

0 赞同 0 条回复

parsons 普通 2024年11月20日下午8:32

”’C++
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
//1.定义左右指针
ListNode *left = head;
ListNode *right = head;
//2.让右指针先跑cnt个点
while(cnt–){
right = right->next;
}
//3.左右指针一起遍历,直到右指针到链表末尾
while(right != nullptr){
left = left->next;
right = right->next;
}
//4.返回left就是倒数第cnt个点
return left;
}
};
时间复杂度O(N)
空间复杂度O(1)

0 赞同 0 条回复

Kisara 普通 2024年11月20日下午8:30

““java
/**双指针，快指针提前移动cnt个距离，然后同时移动，当快指针为空时，漫指针正好停留在倒数第cnt个位置上*/

class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
ListNode p1=head;
ListNode p2=head;
for(int i=1;i<=cnt;i++){
p2=p2.next;
}
while(p2!=null){
p1=p1.next;
p2=p2.next;
}
return p1;
}
}

时间O（N）
空间O（1）

0 赞同 0 条回复

🍊 普通 2024年11月20日下午8:17

“`java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
ListNode p = head, q = head;
while(cnt — > 1) q = q.next;
if(q == null) return head.next;
while(q.next != null){
p = p.next;
q = q.next;
}
return p;

}

直接便利

0 赞同 0 条回复

黑键〰普通 2024年11月20日下午8:14

/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val=undefined ? 0 : val)
* this.next = (next=undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} cnt
* @return {ListNode}
*/
var trainingPlan = function(head, cnt) {
let p0 = head
let p1 = head
while(cnt > 0) {
p1 = p1.next
cnt–
}
while(p1 ! null) {
p0 = p0.next
p1 = p1.next
}
return p0
};
思路：用快慢指针
时间：O(N)
空间：O(1)

0 赞同 0 条回复

苯庸普通 2024年11月20日下午8:11

class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
ListNode fast = head;
ListNode slow = head;
for(int i = 0; i < cnt; i++){
fast = fast.next;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
思路：快慢指针，快指针先走k步，然后快慢一起向后遍历，直到快指针为空，慢指针就是答案
时间 o(n)
空间 o(1)

0 赞同 0 条回复

迢迢星野普通 2024年11月20日下午8:09

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode slow = head, fast = head;
        for (int i = 0; i < cnt; i++) {
            fast = fast.next;
        }

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

使用了快慢指针来解决这道题，通过让快指针先走 cnt 步（让快慢指针在移动时保持着 cnt 个节点的距离），然后快慢指针同时移动，当快指针为 null 时，慢指针指向的节点就是所求的倒数第 cnt 个节点。

时间复杂度：O(n)，需要遍历整个链表一次。
空间复杂度：O(1)，使用了常数级的额外空间。

0 赞同 0 条回复

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

共以下 56 个回答

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

# 回答此问题取消回复

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

共以下 56 个回答

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

# 回答此问题 取消回复

# 回答此问题取消回复