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

剑指offer最优解免费

本问题对应的 leetcode 原文链接：剑指 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)

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
        """
        if head is None:
            return None

        fast = slow = head
        for i in range(k):
            if fast is None:
                return None
            fast = fast.next

        while fast is not None:
            fast = fast.next
            slow = slow.next

        return slow

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) {
        if (head == nullptr) {
            return nullptr;
        }

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

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

        return slow;
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getKthFromEnd(head *ListNode, k int) *ListNode {
    if head == nil {
        return nil
    }

    fast := head
    slow := head
    for i := 0; i < k; i++ {
        if fast == nil {
            return nil
        }
        fast = fast.Next
    }

    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }

    return slow
}

JS

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    if (head == null) {
        return null;
    }

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

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

    return slow;
};

剑指offer题解

发表回复取消回复

后才能评论

control 普通 2024年12月6日下午4:26

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        // 倒数第 cnt 个， 对于数组来说， 应该是倒数 第 cnt -1 个，则 快

        //倒数的做法，肯定是双指针
        if(head == null){return head;}
        //申请两个新指针，
        ListNode fast = head , slow = head;
        //fast 先走 cnt 步
        for(int i =0 ; i < cnt -1 ; i++){
            fast = fast.next;// 其实为了严谨，这里应该也进行一个 为 null 的判断
        }
        //快慢节点，一块走，
        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

这个就看是不是有自我检验了。看着简单，稍不留意就做错了。
1: 解题思路快慢指针
2: 倒数第 n个，这里的n是大于 0 的，但是在数组中，下标都是走 0 开始，这个时候边界问题需要着重考虑下。不小心就会超一个

HU 普通 2024年3月2日上午5:45

/**
 * 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;
};

3_🔥 永久会员 2023年6月21日下午3:58

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        // 快慢指针
        ListNode fast = head;
        ListNode slow = head;
        for(int i = 1;i <= k;i++){
            if(fast == null){
                return null;
            }
            fast = fast.next;
        }
        while(fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

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

    }
};