剑指Offer_编程题（C#实现）_ 链表中倒数第k个结点

题目链表中倒数第k个结点题目描述输入一个链表输出该链表中倒数第k个结点。解题思路解法1遍历链表得到链表的长度n由于单向链表无法从链表尾端回溯所以需要从头节点开始往后走n-k1步就能找到倒数第k个链表了。解法2解法1需要两遍历怎么在遍历一次的前提下就能求得链表的倒数第k个结点呢可以设置两个指针p和q并且都将其初始值置为头p q pListHead;然后让p先走k-1步那么就到了正数第k个结点然后这时候让p和q同时走直到p的下一个结点为空由于两个指针的距离始终保持在k-1所以当第一个指针到达链表尾节点时第二个指针正好走到倒数第k个节点。参考代码解法1/* public class ListNode { public int val; public ListNode next; public ListNode (int x) { val x; } }*/ class Solution { public ListNode FindKthToTail(ListNode head, int k) { // write code here int count 0; ListNode p head; if(head null) return null; while(p ! null) { count; pp.next; } if(count-k 0) return null; phead; for(int i0; icount-k; i) pp.next; return p; } }解法2/* public class ListNode { public int val; public ListNode next; public ListNode (int x) { val x; } }*/ class Solution { public ListNode FindKthToTail(ListNode head, int k) { // write code here ListNode pAhead head; ListNode pBhead head; if(headnull||k0) //判断头节点为空或者k0情况 return null; for(int i0;ik-1;i){ if(pAhead.nextnull){ //防止K的值大于head.next的范围 节点3个k为8 return null; } pAhead pAhead.next; } while(pAhead.next!null){ pAhead pAhead.next; pBhead pBhead.next; } return pBhead; } }