sequence

This paper mainly records the leetcode linked list to find the KTH node

The title

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. Back to list 4->5. Source: LeetCode Link: https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof Copyright belongs to The Buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Answer key

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode getKthFromEnd(ListNode head, int k) { ListNode c1 = head; while (c1 ! = null && k > 0) { c1 = c1.next; k--; } ListNode c2 = head; while (c1 ! = null) { c1 = c1.next; c2 = c2.next; } return c2; }}Copy the code
  • Fast and slow pointer, let the fast pointer take K steps first, and then the two Pointers go synchronously. When the fast pointer goes to the end, the slow pointer is the KTH node from the bottom of the linked list.

summary

The fast pointer takes k steps first, and then the two Pointers move synchronously. When the fast pointer comes to the end, the slow pointer is the KTH node from the bottom of the linked list.

doc

  • lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof