Sword finger offer 22 The penultimate node in the linked list

Title Description

Enter a linked list , Output the last number in the list k Nodes . In order to conform to the habits of most people , From 1 Start counting , That is, the tail node of the list is the last 1 Nodes .

for example , A list has 6 Nodes , Start from the beginning , Their values, in turn, are 1、2、3、4、5、6. The last of the list 3 Each node has a value of 4 The node of .

 Example ：
 Given a linked list : 1->2->3->4->5,  and  k = 2.
 Back to the list  4->5.

Answer key

Traverse twice , The first pass counts the total length of the linked list , Find the positive position of the reciprocal node
Second times , Find the node

1. python

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        cur = head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        cur = head
        count -= k 
        while count:
            cur = cur.next
            count -= 1
        return cur

2. C Language

struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    
    struct ListNode *cur = head;
    int count = 0;
    while (cur != NULL) {
    
        count += 1;
        cur = cur -> next;
    }
    cur = head;
    count -= k;
    while (count != 0) {
    
        count -= 1;
        cur = cur -> next;
    }
    return cur;
}

3.C++

and C equally , Just change a variable declaration

class Solution {
    
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
    
        ListNode *cur = head;
        int count = 0;
        while (cur != NULL) {
    
            count += 1;
            cur = cur -> next;
        }
        cur = head;
        count -= k;
        while (count != 0) {
    
            count -= 1;
            cur = cur -> next;
        }
        return cur;
    }
};