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

本问题对应的 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)

发表回复

后才能评论

评论(11)

  • 。。。。 普通 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;
    
        }
    };