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

剑指offer最优解 8月前 0 198

本问题对应的 leetcode 原文链接：剑指 Offer 22. 链表中倒数第k个节点
本文对应打卡链接：【链表专题】剑指 Offer 22. 链表中倒数第k个节点

问题描述

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

解题思路

视频讲解直达：本题视频讲解

代码实现

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

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

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

        return slow;
    }
}

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

剑指offer题解

发表回复取消回复

后才能评论

。。。。普通 2022年10月27日下午1:57

快慢指针方法
”’cpp
/**
* 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(headnullptr) return head;
ListNode* slow=head;
ListNode* fast=head;
for(int i =0;i<k;i++){
fast=fast->next;
}
while(fast!=NULL)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}
};
”’
空间O（1）时间O（n）

登录以回复

Edison 普通 2022年10月23日下午6:57

思路：fast 比 slow 多走 k 步，然后 slow 和 fast 一起走，当 fast 等于 null 时，slow 正好是倒数第 k 个节点

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        // 判空
        if (head == nullptr) 
            return nullptr;

        // 快慢指针
        ListNode* fast = head; // 快指针
        ListNode* slow = head; // 慢指针

        // fast先走k步
        while (k--) { 
            if (fast == nullptr)
                return nullptr;
            fast = fast->next;
        }

        // 再同时走
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

Monster Dump 普通 2022年10月22日下午7:47

代码实现 (Java)

    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null) {
            return head;
        }
        ListNode curr = head;
        ListNode kNode = head;
        int i = 0;
        while (curr != null && i < k) {
            curr = curr.next;
            i++;
        }
        while (curr != null) {
            kNode = kNode.next;
            curr = curr.next;
        }
        return kNode;
    }

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

勾陈一普通 2022年10月22日下午7:16
/**
* 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) {
/* 使用快慢指针，慢指针从头节点开始，快指针从
从第k个节点开始。当快指针遍历到队尾时，慢指针指向倒数第k个节点 */
ListNode *slow = head, *fast = head;
while(fast != NULL && k–)
{
fast = fast->next;
}
```
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }

    return slow;
}
```
};
登录以回复

泡芙永久会员 2022年10月22日下午6:43

解法：快慢指针
思路：fast 比 slow 多走 k 步，然后 slow 和 fast 一起走，当 fast null 时，slow 正好是倒数第 k 个节点

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

        ListNode fast = head;
        ListNode slow = head;

        // fast 先走 k 步
        for(int i = 0; i < k; i ++) {
            fast = fast.next;
        }

        // fast 和 slow 一起走
        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

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

晨普通 2022年10月22日下午6:09

class Solution(object):
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        #头指针判空
        if not head:
            return null;
        #快、慢指针初始化
        quick, slow = head, head
        #快指针先走k步
        while k > 0:
            quick = quick.next
            k -= 1
        #两指针 一起走，直至快指针走到末尾，输出慢指针
        while quick:
            quick = quick.next
            slow = slow.next
        return slow

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

波波_1936 普通 2022年10月22日下午5:12

    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head==null||k<=0) return head;
        /**
         * 利用快慢指针 快指针和慢指针差就是k
         */
        ListNode fast =head;
        ListNode slow = head;

        while (true){
            if (k>0){
                fast = fast.next;
                k--;
            }else{
                fast = fast.next;
                slow = slow.next;

            }
            if (fast==null){
                break;
            }

        }

        return slow;

    }

时间复杂度O(N) 链表长度为n则遍历了n-k次
空间复杂度O(1) 使用了2个变量

wxc 普通 2022年10月22日上午10:37

额

class Solution(object):
    def getKthFromEnd(self, head, k):
        l = 0
        x = head
        while(x):
            l += 1
            x = x.next
        for i in range(l-k):
            head = head.next
        return head

晨渊普通 2022年10月22日上午10:03

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        //双指针
        if(head == NULL || k<1)
            return head;
        ListNode *fast=head, *slow=head;//定义快指针和慢指针,快指针先走k个节点

        for(int i=1;i<k;i++){  //fast从k位置开始
            fast = fast->next;
        }

        while(fast->next!=NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};
//时间复杂度 O(n)
//空间复杂度O(1)

Spermalow 普通 2022年10月21日下午10:41

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode * currentNode = head;
        // 记录往后走K步的指针
        ListNode * nextKNode = head;
        // 让nextKNode往后走k步
        while (k --) {
            nextKNode = nextKNode->next;
        }
        // 让两个指针同时走，当先走K步的nextKNode指针走到尾后，currentNode即为指向倒数第k个结点位置
        while (nextKNode) {
            nextKNode = nextKNode->next;
            currentNode = currentNode->next;
        }
        return currentNode;
    }
};

🚲南下普通 2022年10月21日下午9:42

class Solution { //快慢指针
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* fast = head;
        ListNode* slow = head;
        for(int i = 0; i < k; i++){ //快指针先走k步
            if(fast == nullptr){
                return nullptr;
            }
            fast = fast->next;
        }
        while(fast != nullptr){ //直到快指针遍历完成，慢指针正好走到倒数第k个
            fast = fast->next;
            slow = slow->next;
        }
        return slow;

    }
};

问题描述

解题思路

代码实现

发表回复 取消回复

评论(11)

发表回复取消回复