題目來(lái)源：?？途W(wǎng)--鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)

題目描述

輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。

解題思路

整體思路就是兩步走，兩人剛開(kāi)始都是1，
第一個(gè)人走到K+1時(shí)，第二個(gè)人也開(kāi)始走，兩個(gè)人速度一樣。
當(dāng)?shù)谝粋€(gè)人走完時(shí)，第二個(gè)人剛好比第一個(gè)人慢了 K

提交代碼

// 整體思路就是兩步走，兩人剛開(kāi)始都是1，
// 第一個(gè)人走到K+1時(shí)，第二個(gè)人也開(kāi)始走，兩個(gè)人速度一樣。
static ListNode method(ListNode head, int k) {
    // 非法輸入
    if (k <= 0 || head == null) {
        return null;
    }

    ListNode result = head;
    ListNode current = head;
    int i = 1;
    for (; current != null; i++) {
        // 如果current已經(jīng)走到了第 K+1 個(gè)，result開(kāi)始往后移
        // 因?yàn)?result 本來(lái)就指向第 1 個(gè)
        if (i > k) {
            result = result.next;
        }
        // 鏈表向后移動(dòng)
        current = current.next;
    }
    return i > k ? result : null;
}

本地測(cè)試代碼

public class FindKthToTail {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode current = head;
        // 生成長(zhǎng)度為5的鏈表
        for (int i = 2; i <= 5; i++) {
            current.next = new ListNode(i);
            current = current.next;
        }
        System.out.println(method(head,0).val);
    }
    
    // 整體思路就是兩步走，兩人剛開(kāi)始都是1，第一個(gè)人走到K+1時(shí)，第二個(gè)人也開(kāi)始走，兩個(gè)人速度一樣。
    static ListNode method(ListNode head, int k) {
        // 非法輸入
        if (k <= 0 || head == null) {
            return null;
        }

        ListNode result = head;
        ListNode current = head;
        int i = 1;
        for (; current != null; i++) {
            // 如果current已經(jīng)走到了第 K+1 個(gè)，result開(kāi)始往后移
            // 因?yàn)?result 本來(lái)就指向第 1 個(gè)
            if (i > k) {
                result = result.next;
            }
            // 鏈表向后移動(dòng)
            current = current.next;
        }
        return i > k ? result : null;
    }
}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}