链表中倒数第k个数

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null || k<1){
            return null;
        }
        ListNode tempA = head;
        for(int i=0;i<k-1;i++){
            if(tempA.next != null){
                tempA = tempA.next;
            }else{
                return null;
            }
        }
        ListNode tempB = head;
        while(tempA.next != null){
            tempB = tempB.next;
            tempA = tempA.next;
        }
        return tempB;
    }
}

概述

鲁棒是英文Robust的音译，有时也翻译成健壮性。所谓的鲁棒性是指程序能够判断输入是否合乎规范要求，并对不符合要求的输入予以合理的处理。

当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表可以让其中一个指针遍历的速度快一些（比如一次在链表上走两步），或者让它先在链表上走若千步

问题

输入一个链表，输出该链表中倒数第k个结点。

思路

为了得到倒数第k 个节点，很自然的想法是先走到链表的尾端，再从尾端回溯k步。可是我们从链表节点的定义可以看出，本题中的链表是单向链表，单向链表的节点只有从前往后的指针而没有从后往前的指针，因此这种思路行不通。

遍历两次

既然不能从尾节点开始遍历这个链表，我们还是把思路回到头节点上来。假设整个链表有n个节点，那么倒数第k • 个节点就是从头节点开始的第n-k+1个节点。如果我们能够得到链表中节点的个数n 那么只要从头节点开始往后走 n-k+1步就可以了。如何得到节点数n,这个不难，只需要从头开始遍历链表，每经过一个节点，计数器加1就行了。

也就是说我们需要遍历链表两次，第一次统计出链表中节点的个数，第二次就能找到倒数第A 个节点。但是当我们把这种思路解释给面试官之后，他会告诉我们他期待的解法只需要遍历链表一次

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);

        FindKthToTail(head,2);
    }
    public static ListNode FindKthToTail(ListNode head, int k) {
        if(head==null){
            return null;
        }
        int count=1;
        ListNode old=head;
        while(head.next!=null){
            head=head.next;
            count++;
        }
        if(k>count){
            return null;
        }
        for(int i=0;i<count-k;i++){
            old=old.next;
        }
        return old;
    }

}

public class ListNode {
       int val;
      ListNode next;

      ListNode(int x) { val = x; }
}

遍历一次

我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。

除此之外，要注意代码的鲁棒性。需要判断传入参数合法性问题。

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 输入的链表不能为空，并且k大于0
    if (n < 1 || head == null) {
        return null;
    }
    // 指向头结点
    ListNode pointer = head;

    // 倒数第k个结点与倒数第一个结点相隔k-1个位置
    // pointer先走k-1个位置
    for (int i = 1; i < n; i++) {
        // 说明还有结点
        if (pointer.next != null) {
            pointer = pointer.next;
        }
        // 已经没有节点了，但是i还没有到达k-1说明k太大，链表中没有那么多的元素
        else {
            // 返回结果
            return null;
        }
    }
    // pointer还没有走到链表的末尾，那么pointer和head一起走，
    // 当pointer走到最后一个结点即，pointer.next=null时，head就是倒数第k个结点
    while (pointer.next != null) {
        head = head.next;
        pointer = pointer.next;
    }
    // 返回结果
    return head;
}


/*
class ListNode {
    int val;
    ListNode next = null;

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

方法2

public static ListNode FindKthToTail(ListNode head,int k) {
        if(head == null) return null;
        ListNode p1 = head,p2 = head;
        while (k>0 && p2 != null){
            p2 = p2.next;
            k--;
        }
        //p2 指向head说明k<=0,p2==null && k>0说明 k超过了链表的长度
        if(p2 == head || (p2 == null && k>0)) return  null;
        while (p2!=null){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }

LeetCode

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 输入的链表不能为空，并且k大于0
    if (n < 1 || head == null) {
        return null;
    }
    // 指向头结点
    ListNode pointer = head;

    // 倒数第k个结点与倒数第一个结点相隔k-1个位置
    // pointer先走k-1个位置
    for (int i = 1; i < n; i++) {
        // 说明还有结点
        if (pointer.next != null) {
            pointer = pointer.next;
        }
        // 已经没有节点了，但是i还没有到达k-1说明k太大，链表中没有那么多的元素
        else {
            // 返回结果
            return null;
        }
    }
    // pointer还没有走到链表的末尾，那么pointer和head一起走，
    // 当pointer走到最后一个结点即，pointer.next=null时，head就是倒数第k个结点
    while (pointer.next != null) {
        head = head.next;
        pointer = pointer.next;
    }
    // 返回结果
    return head;
}

14 剑指offer--链表--链表中倒数第k个数（链表中倒数第k个结点）

链表中倒数第k个数

概述

问题

思路

遍历两次

遍历一次

相关题目

LeetCode