链表中倒数第k个结点

题目描述
输入一个链表,输出该链表中倒数第k个结点。

解题思路
思路1
假设从1开始计数,倒数第k个节点,即为正数n-k+1个节点,可以先统计链表的长度,再遍历查找第n-k+1个节点,需要遍历两次链表。
思路2
定义两个指针,分别指向头结点,第一个指针走k步之后,第二个指针开始移动,当第一个指针达到链表末尾时,第二个节点指向的即使倒数第k个节点。


class ListNode { 
    int val;
    ListNode next = null;

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

public class lianbiaozhongdaoshudikgejiedian { 
    public ListNode FindKthToTail(ListNode head, int k) {

        if (head == null || k <= 0)
            return null;

        int count = 0;
        ListNode pHead = head;
        ListNode plListNode = head;

        while (pHead.next != null) {
            pHead = pHead.next;
            count++;
            if (count >= k) {
                plListNode = plListNode.next;
            }
        }
        if (count < k - 1)
            return null;

        return plListNode;

    }
}
    原文作者:dingpiao190
    原文地址: https://blog.csdn.net/dingpiao190/article/details/77412641
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞