链表中倒数第k个节点
题目描述
输入一个链表,输出该链表中倒数第k个结点。
思路:two-pointers思想,因为是单链表,没法得prevous点,直接遍历得到链表长度再重新遍历效率很低。
采用双指针思想,使得当一个指针处于链表末尾时,另一个指针恰好在倒数第k个节点。
1 public ListNode FindKthToTail(ListNode head, int k) { 2 if(head==null||k==0) 3 return null; 4 ListNode tmp = head; 5 ListNode res = head; 6 //用来计数,得到链表的长度,后续判断k值是否超过了链表长度 7 int i=1; 8 while(tmp.next!=null){ 9 //最终tmp在链表最后一个节点,当tmp的节点位置i>=k时,res开始右移 10 if(i>=k) 11 res = res.next; 12 tmp = tmp.next; 13 i++; 14 } 15 if(i<k) 16 return null; 17 else 18 return res; 19 }