鏈表中倒數第 K 個結點

題目描述

輸入一個鏈表，輸出該鏈表中倒數第k個結點。

題目鏈接: 鏈表中倒數第 K 個結點

代碼

/**
 * 標題：鏈表中倒數第 K 個結點
 * 題目描述
 * 輸入一個鏈表，輸出該鏈表中倒數第k個結點。
 * 題目鏈接：https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
 */
public class Jz14 {

    public ListNode FindKthToTail11(ListNode head, int k) {
        if (head == null || k < 1) {
            return null;
        }
        ListNode tail = head;
        while (tail != null && k > 0) {
            tail = tail.next;
            k--;
        }
        if (k > 0) {
            return null;
        }
        ListNode result = head;
        while (tail != null) {
            result = result.next;
            tail = tail.next;
        }
        return result;
    }


    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k < 1) {
            return null;
        }
        int cnt = 1;
        ListNode node = head;
        while (node.next != null) {
            node = node.next;
            cnt++;
        }
        if (k > cnt) {
            return null;
        }
        ListNode result = head;
        for (int i = 0; i < cnt - k; i++) {
            result = result.next;
        }
        return result;
    }

    /**
     * 方法二：雙指針移動
     * 設鏈表的長度為 N。設置兩個指針 P1 和 P2，先讓 P1 移動 K 個節點，則還有 N - K 個節點可以移動。此時讓 P1 和 P2 同時移動，
     * 可以知道當 P1 移動到鏈表結尾時，P2 移動到第 N - K 個節點處，該位置就是倒數第 K 個節點。
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode FindKthToTail2(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode p1 = head;
        while (p1 != null && k-- > 0) {
            p1 = p1.next;
        }
        if (k > 0) {
            return null;
        }
        ListNode p2 = head;
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        Jz14 jz14 = new Jz14();
        System.out.println(jz14.FindKthToTail(head, 1).val);
        System.out.println(jz14.FindKthToTail2(head, 1).val);
    }
}

【每日寄語】 你的好運氣藏在你的實力裏，也藏在你不為人知的努力裏，你越努力就越幸運。