[数据结构与算法]【DS】链表面试热题之倒数节点及其变体

倒树节点操作核心思路：

双指针：先不同时出发，再同时出发。
模板：

while (k  != 0) {
    if (fast == null) { //链表的长度小于k
        return null;
    }
    fast = fast.next;
    k--;
}
while (fast != null) {
    fast = fast.next;
    slow = slow.next;
}

一、输出链表中倒数最后k个节点

题目描述

1.输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。如果该链表长度小于k，请返回一个长度为 0 的链表。OJ链接

思路分析

1. 本题使用双指针，一个先走k步。然后再一起走，速度均为1
2. 第一个循环条件是k!=0，第二个循环条件是fast!=null

画图分析

AC代码

public ListNode FindKthToTail (ListNode head, int k) {
    ListNode fast = head;
    ListNode slow = head;
    while (k  != 0) {
        if (fast == null) { //链表的长度小于k
            return null;
        }
        fast = fast.next;
        k--;
    }
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

二、删除链表的倒数第n个节点

题目描述

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针。OJ链接

思路分析

1. 这道题是上道题的变体
2. 删除倒数第n个节点的关键是拿到它的前驱节点，这个时候改写上题的函数直接调用
3. 但是这样还不能直接AC，还需要考虑像这样{1,2},2 头结点被删的情况，这个时候定义一个虚拟头节点是再好不过了。

画图分析

AC代码

public ListNode removeNthFromEnd (ListNode head, int n) {
    // write code here
    ListNode res=new ListNode(-1);
    res.next=head;
    ListNode node = FindKthPrevToTail(res, n);
    node.next=node.next.next;
    return res.next;
}
private ListNode FindKthPrevToTail (ListNode head, int k) {
    ListNode fast = head;
    ListNode slow = head;
    while (k != 0) {
        if (fast == null) { //链表的长度小于k
            return null;
        }
        fast = fast.next;
        k--;
    }
    while (fast.next!= null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}