mpweixin用户普通 2024年5月14日上午11:55

打卡成功

0 赞同 0 条回复

刘成志永久会员 2023年10月8日下午8:13

/**
* 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* former = head;
ListNode* latter = head;
while(cnt–)
{
former = former->next;
}
while(former != nullptr)
{
former = former->next;
latter = latter->next;
}
return latter;
}
};
使用双指针，两个指针初始化时间隔要求步数，然后同步移动，直到前面的指针先到链表末尾。
空间复杂度为O(1),时间复杂度为O(n).

0 赞同 0 条回复

mpweixin用户普通 2023年8月23日上午10:32

用双指针
1.初始化：former, latter = head, head
2.构建双指针距离：former向前走k步
3.双指针共同移动：循环中，双指针每轮都向前走一步，直至former走过链表的尾节点跳出
4.返回值：latter

0 赞同 0 条回复

我一定要坚持打卡普通 2023年8月22日下午8:29

思路总结:
使用前后指针，前指针和后指针先相差k-1 个位置，然后让前指针和后指针同时向后移动，直到前指针的next指向空则表明遍历完成，此时后指针指向的就是倒数第k个节点

 package day1;

import java.util.Iterator;

import javax.xml.transform.Source;

public class 剑指Offer22链表中倒数第k个节点 {
    
    public static ListNode getKthFromEnd(ListNode head, int k) {
        if (head==null) {// 先判定head节点
            return head;        
        }
        
        
//      使用双指针法（前后指针）进行查找
//      前后指针差k-1个位置  前指针指向最后一个也就是null的时候，后指针正好指向倒数第k个
        
        ListNode firstListNode =head;
        ListNode lastListNode = head;
//      先将first 指针后移k-1个
        /**
         * 这里使用while循环容易使得前后指针相差多1个，导致结果错误
         */
//      while (firstListNode!=null&& k!=0) {
//          firstListNode=firstListNode.next;
//          k--;
//      }
        
     /**
      *  这里使用for循环      
      */
        for (int i = 1; i < k; i++) {
            if (firstListNode!=null) {
                firstListNode=firstListNode.next;
            }
            System.out.println(i);
        }
//      上边代码执行完成之后，前后指针相差k-1个位置，然后可以一起往后移动，
//      直到前指针指向为空 则表示找到了最后一个
        while (firstListNode.next!=null) {
            firstListNode=firstListNode.next;
            lastListNode=lastListNode.next;
            
        }
        
        
        return lastListNode;
    }
    
    public static void main(String[] args) {
//      这里测试用例 先对list列表赋值一个,再用循环进行插入,不然下边不方便操作
        ListNode list  =new ListNode(0);
        ListNode temp= list;
        for (int i = 1; i < 10; i++) {
            temp.next=new ListNode(i);
            temp=temp.next;
        }
        ListNode temp1=list;
        while (temp1!=null) {
        System.out.println(temp1);
        temp1=temp1.next;
        
    }
        System.out.println("*************");
        /**
         * 这里修改
         */
        temp1=getKthFromEnd(list,3);
        
//      while (temp1!=null) {
//          System.out.println(temp1);
//          temp1=temp1.next;
//          
//      }
        System.out.println(temp1.val);
        
    }

}

0 赞同 0 条回复

黎明之前普通 2023年8月21日下午10:17

//slow为定位的节点
//fast为鉴定整个循环
//先将fast设定到需要的倒数的节点之后slow和fast指针同时移动当fast到最后后退出 slow指向倒数的节点
//判断链表为空和循环链表和链表节点选择不正确和fast指针是否到达最后
if(head NULL)
{
return NULL;
}
ListNode fast=head;
ListNode slow = head;
for(int i =0;i<k-1;i++)
{
if(fast NULL)
{
return NULL;
}
fast = fast.next;
}
while(fast != NULL)
{
slow= slow.next;
fast = fast.next;
}
return slow;

0 赞同 0 条回复

Serena 普通 2023年8月19日下午2:38

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //一个慢指针在头结点
        ListNode slow=head;
        //快指针在头结点后k-1个
        ListNode fast=head;
        for(int i=0;i<k-1;i++){
            fast=fast.next;
        }
        //到快指针到尾节点，慢指针在尾节点前k-1个，也就是倒数第k个
        while(fast.next!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
}

0 赞同 0 条回复

Di questa storia sempre a lie to 普通 2023年8月17日下午8:56

/**
* 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* cur0 = head;
ListNode* cur1 = cur0;
while(cur0 != nullptr)
{
int i = 0;
while(i<k)
{
if(cur1->next nullptr)
{
return cur0;
}
cur1 = cur1->next;
i++;
}
}
return cur0;
}
};
时间复杂度o(n)
空间复杂度o(1)

0 赞同 0 条回复

海浪漂哇漂普通 2023年8月16日下午8:01

时间复杂度o(n)，空间复杂度o(1)
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
for(int i = 1; i <= k; i++){
fast = fast.next;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}

0 赞同 0 条回复

Miracle· 普通 2023年8月15日下午9:48

事件复杂度o(n)，空间复杂度o(1)
思路：使用快慢指针，让快指针先走k步，然后快慢指针一起走，直到快指针为nullptr，返回慢指针
/**
* 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, *fast;
fast = slow = head;
int count = 0;
while (fast != nullptr) {
if (count >= k) slow = slow->next;
fast = fast->next;
count++;
}
return slow;
}
};

0 赞同 0 条回复

Delete隐身普通 2023年8月15日下午9:14

思路：使用快慢指针，快指针先走k个节点，然后快慢指针一起走，当快指针为null时，慢指针指向倒数第k个节点
时间复杂度O(n)，空间复杂度O(1)
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
// 使用快慢指针，快指针先走k个节点，然后快慢指针一起走，当快指针为null时，慢指针就是指向倒数第k个节点
if(head null) {
return null;
}
ListNode fast = head, slow = head;
// 快指针先走k个节点
for(int i = 0; i < k; ++i) {
if(fast null) {
return null;
}
fast = fast.next;
}
// 快慢指针同时走，知道快指针为null
while(fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}

0 赞同 0 条回复

Sheng 永久会员 2023年8月15日下午6:23

时间复杂度O(n)空间复杂度O(1)
思路：双指针
”’java
//单链表删除倒数第K个节点
public class Solution {
public ListNode getKtnFromEnd(ListNode head, int k)
{
ListNode front = head;
ListNode behind = head;
for(int j=0; j<k; j++)
{
front = front.next;
}
while(front.next!=null)
{
front = front.next;
behind = behind.next;
}
return behind;
}
}

0 赞同 0 条回复

mpweixin用户普通 2023年8月15日下午6:17

//首先是计算链表有多少节点
//其次将计算的count-k的值，就是尾节点的值。
//时间复杂度为o(n)
//空间复杂度为o(1)
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
if(headNULL)
return head;

int count=0;
ListNode *out=head;

while(head)
{
    head=head->next;
    count++;
}

for(int i=0;i!=count-k;i++){
    out=out->next;
}
 return out;
}

};

0 赞同 0 条回复

sc_Yang 普通 2023年8月15日下午5:02

时间复杂度：o(m)，空间复杂度o(1)
双指针法：
1、初始化两个指向头部的指针
2、第一个指针先移动k个结点；
3、两个指针开始同时按相同步长移动；
4、第一个指针到末尾时，同时停止两指针；
5、返回第二个指针的位置即是子串的前一个节点；（此处要求返回的就是子串头节点的前一个节点）

/**
 * 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* ptr=head;
        int i = 0;
        while(head){
            if(i == k){
                head = head->next;
                ptr = ptr->next;
            }else{
                head = head->next;
                i++;
            }
        }
        return ptr;
    }
};

0 赞同 0 条回复

谁仁普通 2023年8月15日下午4:11

struct node *findNodeFromEnd(struct node * head, int num)
{
//判断头结点，或者n数字是不是正常
if(head NULL || n <=0)
{
return NULL;
}

struct node * fast = head;
struct node * slow = head;
//fast指针先走n步，我们先走完之后保留在当前位置
while(fast !=NULL && num>1)
{
    fast = fast->next;
    num--;
}
    //同步往后走，知道fast指到链表最末端
while(fast!=NULL)
{
    fast=fast-next;
    slow=slow->next;
}
return  slow;

}

0 赞同 0 条回复

一个人的风海吹了两遍普通 2023年8月15日上午8:15

时间复杂度O（n）
空间复杂度O（1）
快指针先走
两个意外情况为空或不够k个节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
      public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode pre = head;
        if(pre==null)
            return null;
        ListNode tail = head;
        while (k>0){
            //判断是否够k个节点
            if(tail==null)
                return null;
            tail = tail.next;
            k--;
        }
        while (tail!=null){
            pre=pre.next;
            tail=tail.next;
        }
        return pre;

    }
}

0 赞同 0 条回复

帆普通 2023年8月15日上午12:10

// 时间复杂度O(n),空间复杂度O(1)
// 思路：快慢指针
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    let cur = head;
    let pre = head;
    for(let i = 0; i<n; i++){
        pre = pre.next;
    }
    if(pre.next===null) return cur;
    while(pre.next){
        pre = pre.next;
        cur = cur.next;
    }
    return cur;
};

0 赞同 0 条回复

行动派小彩笔普通 2023年8月14日下午10:22

 // 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if(head == NULL) return NULL;
        ListNode* cur = head;
        ListNode* pre = head;
        for(int i=k;i>0;i--)
        {
            if(cur) cur = cur->next;
            else return NULL;
        }
        while(cur!=NULL)
        {
            cur = cur->next;
            pre = pre->next;
        }
        return pre;
    }
};

0 赞同 0 条回复

💮黧大王.exe 普通 2023年8月14日下午10:08

思路：双指针一个快指针一个慢指针，快指针先走k步，之后两者同时前进，当快指针走到最后时，慢指针指的即为所求。
时间复杂度：O(n)
空间复杂度：O(1)
/**
* 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;
for(int i=0;i<k;i++){
fast=fast->next;
}
while(fast!=NULL){
slow=slow->next;
fast=fast->next;
}
return slow;
}
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月14日下午9:52

ListNode* getKthFromEnd(ListNode* head, int k) {
if(head nullptr){
return nullptr;
}
ListNode* forward = head;
ListNode* backward = head;

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

    // k值很大
    if(forward == nullptr){
        return head;
    }

    while(forward){
        backward = backward->next;
        forward = forward->next;
    }

    return backward;
}

0 赞同 0 条回复

只吃酸菜不吃鱼普通 2023年8月14日下午8:52

”’java class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
// 判断特殊情况
if(headnull){
return null;
}
ListNode fast=head,slow=head;
for(int i,i<k,i++){
//判断fast是否先走完
if(headnull){
return null;
}
fast=fast.next;
}
//fast 到达终点的时候，slow刚好在倒数的位置上
while(fast!=null){
fast=fast.next;
slow=slow.next;
}
return slow
}
}

0 赞同 0 条回复

hhhhh 普通 2023年8月14日下午5:13

过

“`cpp
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode *s, *f;
s = f =head;
for(int i = 1; i <= k; i++){ if(f != nullptr){ f = f->next;
}
}
while(f != nullptr){
s = s->next;
f = f->next;
}
return s;
}
};

0 赞同 0 条回复

逸兴遄飞普通 2023年8月14日上午9:30

时间复杂度 O(N)O(N)O(N) ： NNN 为链表长度；总体看， former 走了 NNN 步， latter 走了 (N−k)(N-k)(N−k) 步。
空间复杂度 O(1)O(1)O(1) ：双指针 former , latter 使用常数大小的额外空间。

/**
 * 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 p1 = head, p2 = head;
        // n用来记录当前位置
        int n = 0;
        // 快指针没有走完之前进行操作
        while(p1!=null){
            // 慢指针记录位置在k+1后的所有值
            if(n>=k) p2 = p2.next;
            p1 = p1.next;
            n++;
        }
        // 返回慢指针记录的值即为所求
        return p2;
    }
}

0 赞同 0 条回复

晓宇普通 2023年8月14日上午7:29

class Solution(object):
    def deleteNode(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        if head == None:
            return 
        if head.val == val:
            return head.next

        pre = head
        tmp = head.next

        while(tmp):
            if tmp.val == val:
                pre.next = tmp.next
                tmp = tmp.next
            else:
                pre = tmp
                tmp = tmp.next
        return  head

本题是经典的快慢指针，掌握即可，
主要注意的点还是遍历过程中需要不需要使用头结点，以及快指针应该到哪步停止，
容易走多一步，或者少走一步。
可以先用题中给的case作为测试。

0 赞同 0 条回复

漂洋过海去见你永久会员 2023年8月13日下午5:58

#python题解：快慢指针，快慢指针先指向head，fast先走k步，然后fast&slow一起走，fast走到null时，就说明fast到尾部，即slow就是倒数第k个节点，直接输出slow。
#复杂度：时间复杂度O(n)，空间复杂度O(1)
lass Solution(object):
def getKthFromEnd(self, head, k):
“””
:type head: ListNode
:type k: int
:rtype: ListNode
“””
if head is None:
return None

    slow, fast = head, head
    for i in range(k):
        fast = fast.next

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

    return slow

0 赞同 0 条回复

sincere 普通 2023年8月13日下午5:02

思路：快慢指针遍历，fast先走k步，当fast走到null时，slow刚好走到len-k步，即倒数第K个
复杂度：时间复杂度O(n)，空间复杂度O(1)

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

0 赞同 0 条回复

QQiing 普通 2023年8月13日下午4:47

先计算出链表的长度，再根据k的值，让链表走len-k步
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
if(head NULL){
return NULL;
}
ListNode *temp = head;
int len = 0;
while (temp != NULL) {
len++;
temp = temp->next;
}
for(int i=0; i<len-k; i++){
if(head NULL){
return NULL;
}
head = head->next;
}
return head;
}
};
时间复杂度O(n)，空间复杂度O(1)

0 赞同 0 条回复

辰北、普通 2023年8月13日下午2:43

//1//shijian o(n),俩链表，latter先走k步，然后latter是否为空，不为空就latter=next；为空就return former；2//然后latter是否为空，不为空就latter和former同时->next;否则跳出，return former;
struct ListNode* getKthFromEnd(struct ListNode* head, int k){
if(head NULL)
{
return NULL;
}
struct ListNode *former=head;
struct ListNode *latter=head;
int i=0;
while(k>i){
if(latter->next!=NULL){
latter= latter->next;
// k–;
}
else{
return former;
// k–;
}
i++;

 }
// for(int i=0;i<k;i++){
//     if(latter->next!=NULL){
//         latter=  latter->next;
//     }
//     else{
//         return former;
//     }
// }
 while(latter!=NULL){
     former=former->next;
     latter=latter->next;
 }

     return former;

}

0 赞同 0 条回复

天亮说晚安普通 2023年8月13日上午11:40

思路：双指针法，特殊处理只有一个节点的情况
时间复杂度O(n)，空间复杂度O(1)

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

0 赞同 0 条回复

天亮之前普通 2023年8月13日上午11:11

/**
*打卡
* 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;
    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 条回复

WA 普通 2023年8月13日上午10:37

/**
 * 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* x = head;
        ListNode* y = head;
        for (int i = 0; i < k; i ++){
            x = x -> next;
        }
        while (x){
            x = x -> next;
            y = y -> next;
        }
        return  y;
    }
};
 */
打卡

0 赞同 0 条回复

Jou Siankwa 普通 2023年8月13日上午10:14

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

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        Solution sol = new Solution();
        ListNode kthFromEnd = sol.getKthFromEnd(node1, 2);
        System.out.println(kthFromEnd.val);
    }
}

打卡，简单题，快慢双指针。

0 赞同 0 条回复

Marc 普通 2023年8月13日上午1:12

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

时间O(n) 空间O1

0 赞同 0 条回复

mpweixin用户普通 2023年8月13日上午12:24

时间复杂度：O(N),空间复杂度：O(N)
初始化两个节点，一个比另一个快k-1步，同时走

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fir = head;
        ListNode sec = head;
        int j =k;
        while(j>1){
            sec = sec.next;
            j--;
        }
        while(sec.next != null){
            fir = fir.next;
            sec = sec.next;
        }
        return fir;
    }
}

0 赞同 0 条回复

Prime 普通 2023年8月13日上午12:17

时间复杂度O(n)和空间复杂度O(1)
···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
“””
first = head
second = head
for i in range(k-1):
first = first.next

    while first.next:
        first = first.next
        second = second.next
    return second

···

0 赞同 0 条回复

木子有点甜🍒 普通 2023年8月12日下午11:38

“`python
一开始的思路是把倒数转为正数遍历，然后发现理解错了，又写了一遍

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:
tmp = head
cur = head
#暴力解法：倒数转换为正数，然后几个while循环
# i=0

    # while tmp:
    #     i += 1
    #     tmp = tmp.next
    # tmp = head
    # j = i-k
    # while j!=0:
    #     j=j-1
    #     tmp = tmp.next

    # return tmp

    while tmp.next:
        tmp = tmp.next
        k = k-1

        if k<=0:
            cur = cur.next

    return cur

0 赞同 0 条回复

mpweixin用户普通 2023年8月12日下午11:04

打卡

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

0 赞同 0 条回复

mpweixin用户普通 2023年8月12日下午10:44

這題也是雙指針一快一慢, 快的先走k-1步, 然後慢指針跟快指針同時出發
直到快指針到鏈表尾, 這時返回慢指針就是答案

“`C++
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {

    // handle the head === null
    if (head == NULL) {
        return head;
    }

    ListNode* curr = head;
    ListNode* temp = head;
    int cnt = 1;  // start from 1 
    while(cnt < k) {
        temp = temp->next;
        cnt++;
    }

    while(temp->next != NULL) {
        temp = temp->next;
        curr = curr->next;
    }
    return curr;

}

};

0 赞同 0 条回复

JustRtn 普通 2023年8月12日下午10:19

1.使用快慢指针指向链表头；
2.快指针先走k步，若过程中已经遍历完链表，则返回空；
3.快慢指针同时遍历链表，当快指针指向尾节点时结束遍历，返回慢指针；

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

0 赞同 0 条回复

. 永久会员 2023年8月12日下午9:43

//快慢指针，让快指针先跑k-1步,这时候再让快慢指针一块前进直到快指针的下一步为null
//慢指针所在的位置就是倒数第K个节点
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode p = head;
ListNode q =head;
for(int i=k;i>1;i–){
p = p.next;
}
while(p.next != null){
p = p.next;
q = q.next;
}
return q;
}
}

0 赞同 0 条回复

Scanner 永久会员 2023年8月12日下午9:42

/**
* 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; //head为空

    ListNode* fast = head; //快指针
    ListNode* slow = head; //慢指针
    for (int i = 0; i < k; i++) { //让fast指针与slow指针之间相差k+1位
        if (fast == NULL) {
            return NULL;
        }
        fast = fast->next;
    }

    while (fast != NULL) { //让fast指针走到最后一个元素后 这种情况下slow指针指向的剩余串即为k位
        fast = fast->next;
        slow = slow->next;
    }

    return slow;
}

};

0 赞同 0 条回复

别扒拉我普通 2023年8月12日下午9:33

1、快慢指针，快指针先移动k步，慢指针再开始移动
2、时间复杂度O(n)，空间复杂度O(1)

import java.util.*;

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

public class Solution {

    public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode fast = pHead;
        for(int i=0; i<k; i++){
            if(fast == null){
                return null;
            }
            fast = fast.next;
        }
        ListNode slow = pHead;
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月12日下午9:25

采用快慢指针即可；
时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode p = head;
        ListNode q = head;
        for (int i = k; i > 1; i--) {
            p = p.next;
        }
        while (p.next != null) {
            p = p.next;
            q = q.next;
        }
        return q;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年8月12日下午9:19

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

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

0 赞同 0 条回复

小肸永久会员 2023年8月12日下午9:15

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //fast、slow起始位置为head,fast先走k步，位于第k+1个节点位置（从1开始计数）,链表长度为len。当fast为null时，slow走了len - k步，位于(len - k + 1)个节点位置，也就是倒数第k个节点位置。
        ListNode fast = head, slow = head;
        while (fast != null && k > 0) {
            fast = fast.next;
            k --;
        }
        while (fast != null && slow != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

0 赞同 0 条回复

Joel 普通 2023年8月12日下午9:12

时间复杂度： 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:
        fast = head
        slow = head
        for i in range(k-1):
            fast = fast.next
        while fast.next != None:
            fast = fast.next
            slow = slow.next
        return slow

0 赞同 0 条回复

c 普通 2023年8月12日下午8:57

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

/**
 * 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 pre=head;
        ListNode last=head;
        for (int i = 1; i < k; i++) {
            pre=pre.next;
        }
        while (pre.next!=null){
            pre=pre.next;
            last=last.next;
        }
        return last;
    }
}

0 赞同 0 条回复

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

共以下 46 个回答

Definition for singly-linked list.

class ListNode(object):

def init(self, x):

self.val = x

self.next = None

Definition for singly-linked list.

class ListNode:

def init(self, x):

self.val = x

self.next = None

# 回答此问题取消回复

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

共以下 46 个回答

Definition for singly-linked list.

class ListNode(object):

def init(self, x):

self.val = x

self.next = None

Definition for singly-linked list.

class ListNode:

def init(self, x):

self.val = x

self.next = None

# 回答此问题 取消回复

# 回答此问题取消回复