Topic describes

This is the finger Offer 22 on LeetCode. The KTH node from the bottom of the linked list, and the difficulty is simple.

Tag: linked list, stack, queue, fast and slow pointer

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.Copy the code

Stack/queue solution

One solution to use extra space is to use a stack (queue), where all nodes are pushed into the middle stack (queue) so that the current stack (queue) capacity is CNTCNTCNT.

KKK (CNT − K + 1CNT − K + 1CNT − K +1) elements are then popped from the top of the stack (queue head). The last element that exits the stack (queue head) is the answer.

Code (stack) :

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        Deque<ListNode> d = new ArrayDeque<>();
        while(head ! =null) {
            d.addLast(head);
            head = head.next;
        }
        ListNode ans = null;
        while (k-- > 0) ans = d.pollLast();
        returnans; }}Copy the code

Code (queue) :

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        Deque<ListNode> d = new ArrayDeque<>();
        while(head ! =null) {
            d.addLast(head);
            head = head.next;
        }
        k = d.size() - k + 1;
        ListNode ans = null;
        while (k-- > 0) ans = d.pollFirst();
        returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

Difference method

We can perform a complete traversal of the linked list first, and get the total length CNTCNTCNT. Finally, CNT − KCNT – KCNT − K is the distance between the penultimate KKK node and the headheadhead node.

Code:

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        int cnt = 0;
        ListNode tmp = head;
        while(tmp ! =null && ++cnt > 0) tmp = tmp.next;
        cnt -= k;
        while (cnt-- > 0) head = head.next;
        returnhead; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

How fast a pointer

In fact, we can use the fast or slow pointer.

At the beginning, the fast pointer FAST takes KKK steps first, at which point the distance between FAST and slow is KKK, and then the fast and slow Pointers go together (the relative distance is always KKK). When FAST reaches the end of the list, slow stops at the last KKK node.

Code:

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode slow = head, fast = head;
        while (k-- > 0) fast = fast.next;
        while(fast ! =null) {
            slow = slow.next;
            fast = fast.next;
        }
        returnslow; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

The last

This is the number one in our “Brush through LeetCode” series. The last k node in the linked list starts from 2021/01/01. By the start date, there are 1916 topics in LeetCode, some of which have locks. We will finish all the topics without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.