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

题目：链表中倒数第k个结点

题目描述

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

解题思路

解法1

遍历链表，得到链表的长度n，由于单向链表无法从链表尾端回溯，所以需要从头节点开始往后走n-k+1步，就能找到倒数第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++; p=p.next; } if(count-k < 0) return null; p=head; for(int i=0; i<count-k; i++) p=p.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(head==null||k<=0) //判断头节点为空，或者k<=0情况 return null; for(int i=0;i<k-1;i++){ if(pAhead.next==null){ //防止K的值大于head.next的范围 节点3个，k为8； return null; } pAhead = pAhead.next; } while(pAhead.next!=null){ pAhead = pAhead.next; pBhead = pBhead.next; } return pBhead; } }