Topic describes
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.
Example:
Given a linked list: 1->2->3->4->5, and k = 2.
Return to list 4->5.
Source: LeetCode link: leetcode-cn.com/problems/li… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
Antithesis thought
Assuming that the length of the current linked list is N, then we know that the penultimate KTH node of the linked list is the positive n-k+1 node. At this point, we only need to traverse the n-k+1 node of the linked list in order, which is the penultimate KTH node. We first find the length n of the linked list, and then iterate to the n-k+1 node of the list in order to return.
Answer key code
* 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) { let cur = head,n = 0; While (cur){cur = cur.next; n++; }; cur = head; For (let I = 0; let I = 0; i < n - k; i++){ cur = cur.next; } return cur; };Copy the code