链表中倒数最后k个结点

1、题目

image-20231011125251579

2、解法

1：双指针

思路：第一个指针先移动k步，然后第二个指针再从头开始，这个时候这两个指针同时移动，当第一个指针到链表的末尾的时候，返回第二个指针即可。注意，如果第一个指针还没走k步的时候链表就为空了，直接返回null即可。

public ListNode FindKthToTail(ListNode pHead, int k) {
    if (pHead == null)
        return pHead;
    ListNode first = pHead;
    ListNode second = pHead;
    //第一个指针先走k步
    while (k-- > 0) {
        if (first == null)
            return null;
        first = first.next;
    }
    //然后两个指针在同时前进
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    return second;
}

2：栈

思路：把原链表的结点全部压栈，然后再把栈中最上面的k个节点出栈，出栈的结点重新串成一个新的链表。

public ListNode FindKthToTail(ListNode pHead, int k) {
    Stack<ListNode> stack = new Stack<>();
    //链表节点压栈
    int count = 0;
    while (pHead != null) {
        stack.push(pHead);
        pHead = pHead.next;
        count++;
    }
    if (count < k || k == 0)
        return null;
    //在出栈串成新的链表
    ListNode firstNode = stack.pop();
    while (--k > 0) {
        ListNode temp = stack.pop();
        temp.next = firstNode;
        firstNode = temp;
    }
    return firstNode;
}