题目描述
输入一个链表，输出该链表中倒数第k个结点。
解题思路
1，硬解，先求出链表总长度，然后倒数第k个就是正数第count-k+1个
2，软解，双指针，两个同时开始走，p指针先跑，并且记录节点数，当p指针跑了k-1个节点后，pre指针开始跑， 当p指针跑到最后时，pre所指指针就是倒数第k个节点，也就是说两个指针之间相差k-1，一个到最后，另一个刚好到k
代码实现
/** * */ package 链表; /** * <p> * Title:FindKthToTail * </p> * <p> * Description: * </p> * * @author 田茂林 * @data 2017年8月22日 下午2:32:24 */ public class FindKthToTail { public ListNode NodeFindKthToTail(ListNode head, int k) { if (head == null) { return null; } int count = 1; ListNode p = head; while (p.next != null) { p = p.next; count++; } if (k > count || k < 1) { return null; } p=head; int curcount =1; while(curcount<count-k+1&&p.next!=null){ p=p.next; curcount++; } return p; } //========================================================优化 public ListNode NodeFindKthToTailSuper(ListNode head, int k) { if (head == null) { return null; } if ( k < 1) { return null; } ListNode p = head; for (int i = 1; i < k; i++) { if(p.next!=null) p = p.next; else return null; //用来控制k的长度，防止k的长度超过了总长 } //p到达了指定位置 ListNode pre = head; while(p.next!=null){ p=p.next; pre = pre.next; //p和pre同时出发 } return pre; } }
