关于java:JZ014链表中倒数第-K-个结点

48次阅读

共计 1495 个字符，预计需要花费 4 分钟才能阅读完成。

输出一个链表，输入该链表中倒数第 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);
    }
}