晚睡晚起起不来永久会员 2024年3月28日上午10:11

思路
java
首先特殊情况，头节点是否为空
其次指定快慢指针都指向head
然后对快指针进行前进k个位置，并判断是否到达末尾
慢指针和快指针一起前进，抵达末尾会返回慢指针的位置，这就是倒数第k个节点

// 你的 Java 代码写在这里
class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
//判断特殊情况，头指针是否为空 
         if(head == null){
            return null;
          }
//快慢指针都指向头节点
          ListNode fast = head ,slow = head;
//快指针前进cnt个位置
          for(int i =0 ; i< cnt; i++) {
//判断快指针是否到达尾部
                if(fast == null){
                return null;
            }
//快指针向后移动，输入的值cnt是多少，就向后移动多少，直到抵达末尾活着==或者抵达输入值cnt的大小
            fast = fast.next;
          }
//快慢两个指针一起移动，直到快指针抵达末尾
          while(fast != null){
            fast = fast.next;
            slow = slow.next;
          }
//返回慢指针的值
          return slow;


    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年3月27日下午11:40

class Solution(object):
def trainingPlan(self, head, cnt):
“””
:type head: Optional[ListNode]
:type cnt: int
:rtype: Optional[ListNode]
“””
#删除倒数第K个节点,双指针,一指针先走K-1步
fast=slow=head
if headNone or cnt<=0:
return None
while cnt>0 and fast !=None:
fast=fast.next
cnt-=1
while fast!=None:
fast=fast.next
slow=slow.next
return slow
时间复杂度：O(n),空间复杂度：O(1)

0 赞同 0 条回复

熊猫不是猫普通 2024年3月26日上午10:38

“`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* removeNthFromEnd(ListNode* head, int n) {
ListNode *dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode *slow = dummyHead;
ListNode *fast = dummyHead;
while (fast->next != nullptr && n–) {
fast = fast->next;
}
fast = fast->next;
//fast和slow同时移动，直到fast指向末尾
while(fast != nullptr) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;

    return dummyHead->next;

}

};

“`

0 赞同 0 条回复

钱大牙普通 2024年3月25日下午10:35

快慢指针，快指针先走cnt
class Solution:
def trainingPlan(self, head: Optional[ListNode], cnt: int) -> Optional[ListNode]:
if head is None:
return None
fast = head
slow = head

    for i in range(cnt):
        if fast is None:
            return None
        fast = fast.next
    while fast != None:

        fast = fast.next
        slow = slow.next
    return slow

0 赞同 0 条回复

山月普通 2024年3月14日上午12:05

/**
* 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* a = head;
ListNode* b = head;
while(cnt–)
{a = a->next;}
while(a != NULL)
{
a = a->next;
b = b->next;
}
return b;

};
//自己写的，最后的while判断出现了空指针异常，对于是否是a指向空还是a->next指向空，得有判断，可以画个图

0 赞同 0 条回复

RunAsOne 普通 2024年3月11日下午4:17

第二次打卡

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def trainingPlan(self, head, cnt):
        """
        :type head: Optional[ListNode]
        :type cnt: int
        :rtype: Optional[ListNode]
        """
        fast = head
        slow = head
        for _ in range(cnt):
            fast = fast.next
        while fast:
            fast = fast.next
            slow = slow.next
        return slow

0 赞同 0 条回复

雨落星空普通 2024年3月9日下午6:55

时间复杂度：O(n) 空间复杂度：O(1)
class Solution:
def trainingPlan(self, head: ListNode, cnt: int) -> ListNode:
former, latter = head, head
for _ in range(cnt):
former = former.next
while former:
former, latter = former.next, latter.next
return latter

0 赞同 0 条回复

June 普通 2024年3月6日下午7:08

//使用双指针
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
if (head null || head.next null) {
return head;
}
ListNode first = head;
for (int i = 1; i < cnt; i++) {
first = first.next;
}
ListNode second = head;
while (first.next != null) {
first = first.next;
second = second.next;
}
return second;
}
}

0 赞同 0 条回复

mpweixin用户普通 2024年3月6日下午1:46

时间复杂度O(N),空间复杂度O(1)
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
ListNode* pfast=head;
ListNode* pslow=head;
while(cnt–>1){
pfast=pfast->next;
}
while(pfast->next!=nullptr){
pfast=pfast->next;
pslow=pslow->next;
}
return pslow;
}
};

0 赞同 0 条回复

🌈 普通 2024年3月5日下午10:55

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

};
不需要虚拟头节点，快指针本来就要领先

0 赞同 0 条回复

LAVI 普通 2024年3月5日上午9:03

/**
* 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;
}
int n=1;
ListNode slow = head;
ListNode fast = head;
while(n<cnt){
fast = fast.next;
n++;
}
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
时间复杂复O(n)

0 赞同 0 条回复

C C 普通 2024年3月5日上午2:30

# 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, fast =  head, head
        for _ in range(cnt):
            fast=fast.next
        while fast:
            slow, fast= slow.next, fast.next
        return slow
#时间复杂度 O(n)
#空间复杂度O(1)

0 赞同 0 条回复

e=mc² 普通 2024年3月4日下午11:00

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        // 排除特殊情况
        if (head == null) {
            return null;
        }
        // 定义快慢指针
        ListNode slow = head;
        ListNode fast = head;
        // 快指针先走cnt步
        for (int i = 0; i < cnt; i++) {
            // 快指针的下一节点为null 说明全部走过 直接返回head即可
            if (fast.next != null) {
                fast = fast.next;
            } else {
                return head;
            }
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.next;
    }
}

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

0 赞同 0 条回复

mpweixin用户普通 2024年3月4日下午5:12

public ListNode trainingPlan(ListNode head, int cnt) {
ListNode pre=head,p=head;
while(p!=null&&cnt– >0) p=p.next;
if(pnull) return p;
while(p!=null){
p=p.next;
pre=pre.next;
}
return pre;
}
思路：双指针
时间O(n) 空间O(1)

0 赞同 0 条回复

湘江小水鬼普通 2024年3月4日下午2:23

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode next;
* };
*/
struct ListNode trainingPlan(struct ListNode* head, int cnt) {
struct ListNode* latter = head;
struct ListNode* former = head;
for(int i = 0;i<cnt;i++){
former = former->next;
}
while(former!=NULL){
former = former->next;
latter = latter->next;
}
return latter;
}C语言回答，采用了两个指针进行求解

0 赞同 0 条回复

阿野普通 2024年3月4日下午2:05

#题解
var trainingPlan = function (head, cnt) {
let n = 0;
let cur = head;
while (cur) {
cur = cur.next;
n++;
}
cur = head;
for (let i = 0; i < n – cnt; i++) {
cur = cur.next;
}
return cur;
};

0 赞同 0 条回复

小样板普通 2024年3月4日上午11:55

“` java

思路：快慢双指针的运用，定义两个指针p1和p2，初始时都指向头结点head。然后让p1向前移动k-1次，这样p1就会指向从头开始算起的第(n-k+1)个节点（假设n为链表长度）。接下来同时将p1和p2向前移动，直到p1到达尾部时。此时p2所指向的节点就是倒数第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 k) {
if (head null || k<= 0) return null; // 处理特殊情况

    ListNode p1 = head;
    for (int i = 0; i < k- 1 && p1 != null; ++i) {
        p1 = p1.next;
    }

    if (p1 == null) return null; // 如果p1已经到达尾部，说明不存在倒数第k个节点

    ListNode p2 = head;
    while (p1.next != null) {
        p1 = p1.next;
        p2 = p2.next;
    }

    return p2;
}

}

时间复杂度：O(n)，因为要求完全遍历链表
空间复杂度：O(1)，定义了两个指针，使用了常数大小的空间。

0 赞同 0 条回复

YOLO 普通 2024年3月4日上午11:24

/输入一个链表，输出该链表中倒数第k个节点/
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
if(headnullptr){
return nullptr;
}

    ListNode* slow=head;
    ListNode* fast=head;
    for(int i=0;i < cnt;i++){
        while(fast==nullptr){
            return nullptr; 

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

};

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月4日上午10:48

打卡

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

0 赞同 0 条回复

繁星普通 2024年3月3日下午10:09

class Solution {
//时间复杂度O(n)，空间复杂度O(1)
public ListNode trainingPlan(ListNode head, int cnt) {
//先处理特殊情况
if(head null) {
return head;
}
//双指针：先走cnt步，再一起走
ListNode temp = head;
while(cnt >= 1) {
temp = temp.next;
cnt–;
}
while(temp != null) {
head = head.next;
temp = temp.next;
}
return head;
}
}

0 赞同 0 条回复

东普通 2024年3月3日下午9:19

/**
* 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 pre = head,cur = head;
while(cnt != 0){
cur = cur.next;
cnt–;
}
while(cur != null){
cur = cur.next;
pre = pre.next;
}
return pre;
}
}
//快慢双指针的运用。
时间 O(n) 空间 O（1）

0 赞同 0 条回复

小玉普通 2024年3月3日下午8:04

struct ListNode* trainingPlan(struct ListNode* head, int cnt) {
    typedef struct ListNode Node;
    Node* p = (Node*)malloc(sizeof(Node));
    p->next = head;
    Node* q = (Node*)malloc(sizeof(Node));
    q = p;
    int i = 0;  
    while (q->next != NULL) {
        i++;  // 当还没有到达第cnt个结点时，只有q动
        if (i < cnt) {
            q = q->next;
        } else { // 当p和q距离为cnt时，则当q到达最后一个结点后，p在倒数第cnt个位置上
            p = p->next;
            q = q->next;
        }
    }
    return p;
}
时间 O(n) 空间 O（1）

0 赞同 0 条回复

=.= 普通 2024年3月3日下午7:27

/**
* 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 dummy = new ListNode(-1);
// dummy.next = head;

    ListNode p = head;
    for(int i=0; i<cnt; i++){
        p = p.next;
    }

    ListNode cur = head;
    while(p != null){
        p = p.next;
        cur = cur.next;
    }

    return cur;
}

}

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

0 赞同 0 条回复

一颗红豆普通 2024年3月3日下午4:11

时间复杂度o（n），空间复杂度o（1）
注意头为空和列表长度不够k的特殊情况
快慢指针遍历列表，快指针先走k步，在同时走，当快指针为空时，慢指针所处位置即为倒数第k个位置
/**
* 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(headnullptr)
{
return nullptr;
}
ListNode *fast = head;
ListNode *slow = head;
for(int i =0 ;i < cnt; i++)
{
if(fastnullptr)
{
return nullptr;
}
fast = fast->next;

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

}

};

0 赞同 0 条回复

一期一会普通 2024年3月3日下午3:17

使用双指针，设置temp指针先走cnt – 1次，此时aim指针和temp指针同时走，当temp遍历完链表后，aim指向所求节点
时间复杂度 O(n), 空间复杂度O(1)

/**
 * 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 *temp = head;
        ListNode *aim = head;
        for(int i = 0; i < cnt - 1; i++)
        {
            temp = temp->next;
        }
        while(temp->next != NULL)
        {
            temp = temp->next;
            aim = aim->next;
        }
        return aim;
    }
};

0 赞同 0 条回复

一个达不刘普通 2024年3月3日上午11:32

双指针，遍历出cnt长度，再同时向表尾遍历。有一个指针走到表尾时，另一个指针就是倒数cnt位置。
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
ListNode *pre=head, *cur = head;

    for(int i = 0;i < cnt;i++){
        cur = cur->next;
    }

    while(cur != nullptr){
        pre = pre->next;
        cur = cur->next;
    }

    return pre;
}

};

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

0 赞同 0 条回复

Sam 普通 2024年3月3日上午2:13

class Solution(object):
def trainingPlan(self, head, cnt):
“””
:type head: Optional[ListNode]
:type cnt: int
:rtype: Optional[ListNode]
“””
slow, fast = head, head
for i in range(cnt):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
return slow

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

0 赞同 0 条回复

刘超波普通 2024年3月2日下午10:18

/**
* 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 f = head;
ListNode s = head;
while (cnt!=0)
{
f = f.next;
cnt–;
}
while (f!=null)
{

    f = f.next;
    s = s.next;
    }

    return s;

}

}提交

0 赞同 0 条回复

mpweixin用户普通 2024年3月2日下午10:00

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年3月2日下午9:14

python实现
整体思想双指针方法
p1,p2
1.p1先循环cnt次
2.p1再次循环，直到链表尾部，此时循环次数为len(链表)-cnt
p1循环的同时p2也在循环，当循环结束的时候，p2刚好是倒数第cnt个
3.return p2即可
需要考虑的特殊情况
如果cnt大于链表的长度那么直接返回
时间复杂度：o(n)
空间负责度：o(1)

0 赞同 0 条回复

Augenstern 普通 2024年3月2日下午7:59

代码:”’java
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy=new ListNode(0,head);
int length =getLength(head);
ListNode cur = dummy;
for(int i=1;i<length-n+1;++i){
cur=cur.next;

    }
    cur.next=cur.next.next;
    ListNode ans = dummy.next;
    return ans;

}
public int getLength(ListNode head){
    int length=0;
    while(head!=null){
        ++length;
        head=head.next;
    }
    return length;
}

}

0 赞同 0 条回复

mpweixin用户普通 2024年3月2日下午6:50

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

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

0 赞同 0 条回复

恭喜发财💰 普通 2024年3月2日下午6:49

”’java
//代码
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
ListNode node1=null;
ListNode node2=null;
node1=head;
node2=head;
if(head.nextnull){
return head;
}
for(int i=1;i<cnt;i++){
node2=node2.next;
}
while(node2.next!=null){
node1=node1.next;
node2=node2.next;
}
return node1;
}
}

0 赞同 0 条回复

零普通 2024年3月2日下午6:32

思路：快慢指针，复杂度：O(n)
代码：

“`java

public ListNode trainingPlan(ListNode head, int cnt) {
    ListNode node1 = head;
    ListNode node2 = head;
    while (null != node1 && cnt > 0) {
        node1 = node1.next;
        --cnt;
    }

    while (node1 != null) {
        node1 = node1.next;
        node2 = node2.next;
    }
    return node2;
}

0 赞同 0 条回复

哆啦A梦的面包普通 2024年3月2日下午5:56

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func trainingPlan(head *ListNode, cnt int) *ListNode {
    n := 0
    for node := head; node != nil; node = node.Next {
        n++
    }
    for k = head; n > cnt; n-- {
        k = k.Next
    }
    return
}

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

0 赞同 0 条回复

demon 普通 2024年3月2日下午5:22

解题思路：快指针先走k步，快慢指针同时走\n\n具体过程：开始快慢指针都指向头结点，先让快指针走k步，然后快慢指针同时走，当快指针走到空的时候，慢指针的位置即为链表倒数第k个结点的位置。\n\n要注意的是，k的长度可能大于链表结点的长度，fast先走k步会走到空，因此还要要判断fast是否走到空，如果走到空，则返回空。\n\n\n\n
/**
* 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(cnt–)
{
if(fastNULL)
{
return NULL;
}
fast=fast->next;
}
while(fast)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}
};

0 赞同 0 条回复

Jankin 普通 2024年3月2日下午5:00

/**
 * 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 slow = head, fast = head;
        for (int i = 0; i < cnt; 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 条回复

莫～慢～待普通 2024年3月2日下午4:50

class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode virHead=new ListNode(-1);
virHead.next=head;
ListNode fast,slow;
fast=virHead;
slow=virHead;
for(int i=0;i<=n;i++)
fast=fast.next;
while(fast!=null&&slow!=null)
{
fast=fast.next;
slow=slow.next;
}
ListNode temp=slow.next;
slow.next=temp.next;
return virHead.next;
}
}
利用虚拟节点辅助删除节点操作。利用快慢指针锁定位置，其中快的比慢的多走k+1步，锁定被删除节点的前一个位置，就可以删除目标节点。
时间复杂度O(n)
空间复杂度O(1)

0 赞同 0 条回复

言之命至普通 2024年3月2日下午4:49

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



    }
}

双指针问题
fast指针先走k步，当fast走到第k步，slow指针开始出发。
两个指针保持相同的步长，当fast为便利完成时，
slow指针指向的就是目标节点。

时间复杂度O(n)：最差情况返回倒数第1的节点。
空间复杂度O(1)：两个指针占用常量空间。

0 赞同 0 条回复

mpweixin用户普通 2024年3月2日下午4:41

让一个指针先走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 removeNthFromEnd(ListNode head, int n) {
ListNode temp = new ListNode(0 , head);
ListNode pre = head;
ListNode second = temp;
for(int i = 0; i < n; i++){
pre = pre.next;
}
while (pre != null){
pre = pre.next;
second = second.next;
}
second.next = second.next.next;
ListNode ans = temp.next;
return ans;
}
}

0 赞同 0 条回复

Deckkker 普通 2024年3月2日下午4:25

# 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]:
        fast = head
        slow = head
        while cnt:
            fast = fast.next
            cnt -= 1

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

双指针
fast指针先走k步，
当fast走到第k步，slow指针同时出发。
两个指针保持相同的步长，当fast为None时，
slow指针指向的就是目标节点。

时间复杂度O(n)：最差情况返回倒数第1的节点。
空间复杂度O(1)：两个指针占用常量空间。

0 赞同 0 条回复

lucky耶耶耶*👻*～普通 2024年3月2日下午4:19

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here 
        if (pHead == null) {
            return null;
        }
        ListNode fast = pHead, slow = pHead;
        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 条回复

kfaebot 普通 2024年3月2日下午4:07

“`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;

        //快指针先走cnt步
        for(int i=0;i<cnt;i++){
            fast=fast->next;
        }
        //快慢指针保持间隔cnt一起走
        while(fast!=nullptr){
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
}

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

“`

0 赞同 0 条回复

mpweixin用户普通 2024年3月2日下午3:25

让快指针先走cnt步，随后快慢指针一起走，则快指针到底时慢指针就是倒数第cnt个
时间复杂度$O(n)$，空间复杂度$O(1)$

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode front = head, behind = head;
        while(front != null && cnt >0){
            front = front.next;
            cnt--;    //让front先走k步
        }
        while(front != null){
            front = front.next;
            behind = behind.next;
        }
        return behind;
    }
}

0 赞同 0 条回复

NULL 普通 2024年3月2日下午2:41

/**
* 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 removeNthFromEnd(ListNode head, int n) {
ListNode dumpyHead = new ListNode(-1,head);
ListNode slow = dumpyHead;
ListNode fast = dumpyHead;
for(int i = 0 ; i < n; i++){
fast = fast.next;
}
while(fast.next != null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dumpyHead.next;
}
}
时间复杂度O(n)
空间复杂度O(1)

0 赞同 0 条回复

墨丘俐普通 2024年3月2日下午2:07

/**
* 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 slow = head;
ListNode fast = head;
//fast走cnt，与slow间隔为cnt
for(int i = 0;i<cnt;i++){
fast = fast.next;
}
//共同往后走，间隔cnt个，fast走到null即可
while(fast!=null){
slow = slow.next;
fast = fast.next;

    }
    return slow;

}

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

0 赞同 0 条回复

望普通 2024年3月2日下午12:58

“`python
class Solution:
def trainingPlan(self, head: Optional[ListNode], cnt: int) -> Optional[ListNode]:
pre, cur = head, head

    while cnt> 0:
        cur = cur.next
        cnt= cnt - 1

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

    return pre

双指针，倒数第K个，先让前指针走K步，前指针为空，返回cur值
时O(N)
空O(1)

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月2日上午11:53

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

        ListNode fast=head;
        ListNode slow = head;


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

        return slow;
    }
}

时间复杂度O（n)

0 赞同 0 条回复

神经蛙普通 2024年3月2日上午11:14

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode next;
* };
*/
struct ListNode trainingPlan(struct ListNode* head, int cnt) {

struct ListNode *n1 = NULL;
struct ListNode *n2 = NULL;
n1 = head;
n2 = head;

while(cnt--)
{
    n2= n2->next;
}

while(n2){
    n2 = n2->next;
    n1 = n1->next;
}
return n1;

}
时间复杂度：O（N）；空间复杂度O(1)

0 赞同 0 条回复

ChenZhangHangTime 永久会员 2024年3月2日上午11:09

这题大概的思路是：快指针先走k步，然后快慢指针一起走，直到快指针指向空的时候，快慢指针刚好是倒数第k个
代码：
1.先判断空指针异常
2.快指针先走k步
3.快慢指针此时同时开始往后走，当快指针为空时，慢指针刚好是倒数第k个
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;
}

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

0 赞同 0 条回复

Yuki 永久会员 2024年3月2日上午10:39

class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
ListNode*dummyhead=new ListNode(0);
dummyhead->next=head;

    ListNode*slow=dummyhead;
    ListNode*fast=dummyhead;

    while(cnt--){
        fast=fast->next;
    }
    while(fast->next!=nullptr){
        slow=slow->next;
        fast=fast->next;
    }
    ListNode*tmp=slow->next;
    slow->next=slow->next->next;

    return tmp;
}

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

0 赞同 0 条回复

Bing0 普通 2024年3月2日上午10:13

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* trainingPlan(struct ListNode* head, int cnt) {
    if(head == NULL)
        return NULL;
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(cnt > 0){
        if(fast == NULL)
            return NULL;
        fast = fast->next;
        cnt--;
    }
    while(fast != NULL){
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

使用快慢双指针，fast指针先走cnt步，然后slow指针和fast指针一起走直到fast为空，此时的slow就是倒数第cnt个节点。
时间复杂度O(n);
空间复杂度O(1).

0 赞同 0 条回复

😴 普通 2024年3月2日上午9:44

/**
* 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 fast = head;
ListNode slow = head;
for(int i = 0; i < cnt;i++){
if(fast null){
return null;
}
fast = fast.next;

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


}

}
首先要判断头结点是否为空，创建一个快结点，使其在慢结点后k个位置，此时要注意，万一该链表没有k个结点，后面快和慢同时往后移，当快为空，慢刚好指向倒数第k个结点。
时间复杂度O(n)
空间复杂度O(1)

0 赞同 0 条回复

HU 普通 2024年3月2日上午9:33

/**
 * 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) {
    // 设置哑节点
    const dummy = new ListNode(-1, head);

    // 设置快慢指针
    let slow = dummy;
    let fast = dummy;

    // 令快指针向前先移动cnt个单位
    for(let i = 0; i < cnt; i++) {
        fast = fast.next;
    }

    // 让快指针和慢指针同时移动到快指针指向结尾
    while(fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    return slow;
};

0 赞同 0 条回复

mpweixin用户普通 2024年3月2日上午9:31

“`java
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
ListNode slow = head, quick = head;
while (cnt– != 0) {
quick = quick.next;
}
while (quick != null) {
quick = quick.next;
slow = slow.next;
}
// slow 和 quick 相差 cnt， quick到了尾节点之后 -> slow和尾节点相差 cnt – 1
return slow;
}
}
“`java

1 赞同 0 条回复

Free 普通 2024年3月2日上午8:22

/**
 * 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, *fast = head;
        for(int i = 0; i < cnt; i++)
            fast = fast->next;
        while(fast)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

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

0 赞同 0 条回复

Yox 普通 2024年3月2日上午4:55

Definition for singly-linked list.

class ListNode:

def init(self, x):

self.val = x

self.next = None

class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
A = headA
B = headB
while A!=B:
A = A.next if A else headB
B = B.next if B else headA
return A

    至若链表者，寻同为其上，逐求为其下。

时间 O（n+m）
空间O（1）常数时间

0 赞同 0 条回复

！。！普通 2024年3月2日上午12:08

/**
* 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* newHead = new ListNode();
newHead->next = head;
ListNode* fast = new ListNode();
ListNode* slow = new ListNode();
fast = newHead;
slow = newHead;
for(int i=0; i<cnt; i++){
fast=fast->next;
}
while(fast->next != NULL){
slow=slow->next;
fast=fast->next;
}
return slow->next;

};

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

0 赞同 0 条回复

Laboratory 普通 2024年3月1日下午11: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 removeNthFromEnd(ListNode head, int n) {
        // 快慢指针
        ListNode fast = head;
        // 在头节点前设置虚拟节点，这样可以使慢节点指向倒数第k个节点的前驱节点
        ListNode slow = new ListNode(-1);
        slow.next = head;
        // 先让快指针走K步
        while(n-- > 0) {
            fast = fast.next;
        }
        // 特殊处理头节点
        if(fast == null) {
            return head.next;
        }
        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

实现思路见注释

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

0 赞同 0 条回复

Let it be 永久会员 2024年3月1日下午11:10

class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
if(head null){
return null;
}
ListNode qk = head;
ListNode sl = head;
while(cnt>0){
qk = qk.next;
cnt-=1;
}
while(qk != null){
qk = qk.next;
sl = sl.next;
}
return sl;
}
}
时间复杂O（n）空间复杂O（1）

0 赞同 0 条回复

在线coding 普通 2024年3月1日下午11:10

/**
* 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 {
/**
* 时间复杂度O(n),空间复杂度O(1)
*/
public ListNode trainingPlan(ListNode head, int cnt) {
if (head null) {
return null;
}
// 创建虚拟头节点
ListNode dumyNode = new ListNode(-1, head);
// 快慢指针
ListNode fastNode = dumyNode;
ListNode slowNode = dumyNode;
// 让快指针先移动n+1
for (int i = 0; i <= cnt; i++) {
fastNode = fastNode.next;
}
// 快慢指针同时移动，直到快指针到尾部
while (fastNode != null) {
fastNode = fastNode.next;
slowNode = slowNode.next;
}
// 直接返回慢指针的下一个节点
return slowNode.next;
}
}

0 赞同 0 条回复

统一绿茶Gin 普通 2024年3月1日下午11:08

链表中倒数第cnt个节点,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) {
        if(head == null)
            return null;

        ListNode fast = head, slow = head;
        int k = cnt;
        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 条回复

while(1) 普通 2024年3月1日下午10:56

“`C++
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 != nullptr)
{
former = former->next;
latter = latter->next;
}
return latter;
}
};
“`
方法：双指针
时间复杂度：o(n)
空间复杂度：o(1)

0 赞同 0 条回复

紫芝普通 2024年3月1日下午10:43

时间复杂度：O(n)
空间复杂度：O(1)
思路：双指针（fast，slow），让fast先前进cnt步，然后fast和slow一起走，当fast\=\=nullptr时，此时的slow即为倒数第cnt个节点。

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

如有问题，欢迎指正，谢谢！

0 赞同 0 条回复

机电皮怪永久会员 2024年3月1日下午10:34

时间复杂度o（2n）
空间复杂度o（1）
###c++

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if ( headA == nullptr || headB == nullptr )
        {
            return nullptr;
        }

        ListNode* A = headA;
        ListNode* B = headB;
        while ( A != B )
        {
            A = A == nullptr ? headB : A->next;
            B = B == nullptr ? headA : B->next;
        }

        return A;
    }
};

0 赞同 0 条回复

神经蛙普通 2024年3月1日下午10:26

class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
// 特判
if(head null) return null;

    ListNode i = head;
    ListNode j = head;

    // 快指针先跑cnt次
    for(int k = 0; k < cnt; k++){
        if(i == null) return null;
        i = i.next;
    }

    // 逐步移动
    while(i != null){
        i = i.next;
        j = j.next;
    }

    return j;

}

}

0 赞同 0 条回复

普通 2024年3月1日下午10:05

class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
ListNodep=head,q=head;
for (int i=cnt;i>0;i–) p=p->next;
while(p!=nullptr)
{
p=p->next;
q=q->next;
}
return q;
}
};
打卡

0 赞同 0 条回复

Raphtalia. 普通 2024年3月1日下午9:53

/**
* 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) {
// 倒数第k个节点是整数第n-k个节点，使用快慢指针的方法。
if(head nullptr) return nullptr;
ListNode* fast = head;
ListNode* slow = head;
while(cnt–){
fast = fast->next;
}
while(fast != nullptr){
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
时间复杂度O（n），空间复杂度O（1）

0 赞同 0 条回复

王位詮釋普通 2024年3月1日下午9:50

···java
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
ListNode first = head;
ListNode second = head;
int i = 0;
while(i<cnt){
first = first.next;
i++;
}
while(first!=null){
first = first.next;
second = second.next;
}
return second;
}
}
时间复杂度：只遍历了一次链表，O(n)，空间复杂度为O(1)，额外设置了first和second两个指针。
思路：先让first走cnt步，随后first和second一起走，当first为null的时候，second刚好为第cnt个节点。

0 赞同 0 条回复

还不多喝热水普通 2024年3月1日下午9:45

/**
 * 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) {
        // 快指针指向头节点并先走 cnt 步
        ListNode fast = head;
        for(int i = cnt; i > 0; i--) {
            fast = fast.next;
        }
        // 慢指针指向头节点
        ListNode slow = head;
        // 如果快指针不为空，则快慢指针均向后移动
        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 如果快指针为空直接返回慢指针
        return slow;
    }
}

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

0 赞同 0 条回复

时生普通 2024年3月1日下午9:28

//双指针法，p与q之间的距离为k时，但p走到NULL时，q就指向倒数第k个结点
struct ListNode* trainingPlan(struct ListNode* head, int cnt) {
typedef struct ListNode ListNode;
ListNode *p =head, *q=head;
int i=0;
while(i<cnt){
p = p->next;
i++;
}
while(p!=NULL){
p = p->next;
q = q->next;
}
return q;
}

0 赞同 0 条回复

进取普通 2024年3月1日下午9:23

打卡

0 赞同 0 条回复

Yeah~ 普通 2024年3月1日下午9:20

/**
* 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* pre = head, * post = head;
    while(cnt--){
        post = post->next;
    }
    while(post!=nullptr){
        post = post->next;
        pre = pre->next;
    }
    return pre;


}

};
首先判空，让post指针先走cnt个，然后pre和post指针一起走，当post指针为空时，pre指针位置正好

0 赞同 0 条回复

30tcq 普通 2024年3月1日下午9:16

思路
两次遍历，第一遍统计长度len，第二遍检索倒数第cnt个（即正数len+i- 1个，1为起点）训练项目的编号

/**
 * 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) {
        int len = 0;
        ListNode *newhead = head;
        while(newhead->next != NULL){
            len++;
            newhead = newhead->next;
        }

        int i = 0;
        ListNode *tmp = head;
        while(i < len - cnt + 1){
            i++;
            tmp = tmp->next;
        }
        return tmp;
    }
};

思考费力的点
遍历的次数+起点+终止条件的确定
时间复杂度
O(n)
空间复杂度
O(1)

0 赞同 0 条回复

叫不醒装睡的人普通 2024年3月1日下午9:12

class Solution {
    // 根据题意，获取的是从倒数第 k 个节点开始的链表
    // 采用快慢指针方法来解决
    // 避免空节点
    // 快指针比慢指针领先 (cnt - 1) 步
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode cur = head, pre = head;
        int step = cnt - 1;
        while (step > 0) {
            cur = cur.next;
            step -= 1;
        }
        if (cur == null) {
            return null;
        }
        while (cur != null && cur.next != null) {
            cur = cur.next;
            pre = pre.next;
        }
        return pre;
    }
    // 解题代码时间复杂度为 O(n)
    // 因为 cur 指针需要遍历整个链表
    // 空间复杂度为 O(1) 
    // cur pre step 这三个局部变量占用常数
}

0 赞同 0 条回复

云无深雁影普通 2024年3月1日下午9:06

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

}
双指针
时间复杂度On
空间复杂度O1

0 赞同 0 条回复

Monou 普通 2024年3月1日下午8:55

快慢指针
/**
* 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 newHead = new ListNode(0);
newHead.next = head;
ListNode last = newHead;
ListNode fast = newHead;
while(cnt– > 0){
fast = fast.next;
}
while(fast != null){
fast = fast.next;
last = last.next;
}
return last;
}
}

复杂度O（n)

0 赞同 0 条回复

heathhou 普通 2024年3月1日下午8:55

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

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

思路：双指针。先计算好快慢指针之间的距离为题目所要求的的数，然后同时向后移动，当快指针到链表结尾的时候，慢指针所指向的节点就是所求的节点。
时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

Jimmy 普通 2024年3月1日下午8:55

快慢指针，快指针要比慢指针快cnt

/**
 * 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,*fast = head;
        if(slow == nullptr) return nullptr;
        while(cnt--){
            fast = fast->next;
        }
        while(fast != nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

0 赞同 0 条回复

铭命鸣普通 2024年3月1日下午8:54

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return head;
        }

        if (head.val == val) {
            return head.next;
        }

        ListNode temp = head.next;

        ListNode pre = head;

        while (temp != null) {
            if (temp.val == val) {
                pre.next = temp.next;
                return head;
            } else {
                pre = temp;
                temp = temp.next;
            }
        }

        return head;
    }
}

0 赞同 0 条回复

　南木普通 2024年3月1日下午8:54

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

/**
 * 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) {
        int count = 0;
        ListNode node = head;
        while(node != null){
            node = node.next;
            count++;
        }

        node = head;
        for(int i = 0;i < count - cnt;i++)
        {
            node = node.next;
        }

        return node;
    }
}

0 赞同 0 条回复

是hua不是pua 普通 2024年3月1日下午8:50

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

快慢指针

0 赞同 0 条回复

MARS 普通 2024年3月1日下午8:41

day1 第二道题

function trainingPlan(head: ListNode | null, cnt: number): ListNode | null {
    //查找倒数第几个，典型快慢指针，快指针先走k-1个
    let fast :ListNode|null = head,slow :ListNode|null= head
    let k :number = cnt-1  //k-1步是指，从最后一个节点开始，走一步是倒数第二个
    while(k--){
        fast = fast.next  //快指针先走k步
    }
    while(fast && fast.next){  //确保可以继续走
        fast = fast.next
        slow = slow.next
    }
    return slow
};

0 赞同 0 条回复

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

共以下 83 个回答

Definition for singly-linked list.

class ListNode:

def init(self, x):

self.val = x

self.next = None

# 回答此问题取消回复

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

共以下 83 个回答

Definition for singly-linked list.

class ListNode:

def init(self, x):

self.val = x

self.next = None

# 回答此问题 取消回复

# 回答此问题取消回复