Input a linked list, output the last KTH node of the list. In order to conform to the convention of most people, this case counts from 1, i.e. the last node of the list is the last node from the last.

For example, a linked list has six nodes, starting with the head node, whose values are 1, 2, 3, 4, 5, and 6. The third from last node of the list is the node with the value 4.

Source: LeetCode

Example:

Given a linked list: 1->2->3->4->5, and k = 2. Return to list 4->5.Copy the code

preface

I have done both offer and Leetcode before. Leetcode is easy. Today’s daily problem again encountered, old problem new to do.

Recently, I tried to spare some time from work to do a detailed solution to the daily Leetcode problem with various solutions. As Feynman learning method said, after understanding to be able to output, to teach to promote learning. Today we’ll have 5 solutions: normal double traversal, double pointer, recursion, stack, hash. Divergent thinking, for easy title punch! Like your comments at 👍🏻

Method 1:

  1. First count the list length. The penultimate KTH node = the length of the list -k.
  2. Then start from the beginning, the control condition is the list length > K. And the node that you’re going to be at is the node that you’re at.

This topic is simple, or do not understand, begin to draw on the paper to understand.

# # # code

/** * 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 *temp = head;
        int length = 0;
        while(temp ! =NULL) {
            length++;
            temp = temp->next;
        }
        temp = head;
        while (length > k) {
            temp = temp->next;  
            length--;
        }
        returntemp; }};Copy the code

Solution 2: Dual Pointers

  1. Declare two Pointers. Fast takes k steps first.
  2. Then another slow starts walking from the beginning, while fast continues walking. Step 1
  3. Until Fast is NULlpt, then the node pointed by slow is the penultimate KTH node.

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        / / double pointer
        ListNode *fast = head;
        ListNode *slow = head;
        while (k > 0) {
            fast = fast->next;
            k--;
        }
        while(fast ! =NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        returnslow; }};Copy the code

Solution 3: Recursion

The recursive process is thought of as an oscillating wave that oscillates around and around and hits NULL on the linked list. And then it reverberates, and there’s a variable that keeps track of how many times it reverberates. When the number of echoes equals k, the current node is the node in question.

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if(head == NULL) return NULL;
​
        ListNode *temp = getKthFromEnd(head->next, k);
        if(temp) return temp;
        cr++;
        if(cr == k) return head;
        return nullptr;
    }
private:
int cr = 0 ;
};
Copy the code

Solution 4: Stack

First, all the stack is pressed, and then k-1 nodes pop up. At this time, the top node of the stack is the desired node.

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        stack<ListNode*> temp;
        while(head) {
            temp.push(head);
            head = head->next;
        }
        while(k > 1) {
            temp.pop(a); k--; }return temp.top();
    }
};
Copy the code

Solution 5: Hash table

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        unordered_map<int, ListNode *> hash;
        int length = 0;
        ListNode *temp = head;
        while(temp) {
            hash[length] = temp;
            temp = temp->next;
            length++;
        }
        unordered_map<int, ListNode*>::iterator it;
        it = hash.find(length - k);
        returnit->second; }};Copy the code

other

Other algorithms are solved in detail

Leetcode Portal Welcome to like comment favorites 👍🏻