剑指offer | 链表中的倒数第K个结点 | 12

目录

• 思路分析

思路分析

这个题目也没有什么很好的解决方法.

首先先遍历一次链表,求出这个链表的长度n.

倒数第k个,其实就是正数n-k+1个.

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) {
        ListNode* p = head;
        int len=0;
        while(p){
            len++;
            p=p->next;
        }
        if(k>len)return NULL;
        p = head;
        k = len-k+1;
        for(int i=1;i<k;i++){
            p = p->next;
        }
        return p;
    }
};

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:
        p = head
        len = 0
        while p:
            len+=1
            p = p.next;
        if k>len:return None
        k = len - k + 1
        p = head
        for i in range(1,k):
            p = p.next
        return p