本文共 710 字,大约阅读时间需要 2 分钟。
输入一个链表,输出该链表中倒数第k个结点。
为了能够只遍历一次就能找到倒数第k个节点,可以定义两个指针:
(1)第一个指针从链表的头指针开始遍历向前走k-1,第二个指针保持不动;
(2)从第k步开始,第二个指针也开始从链表的头指针开始遍历;
(3)由于两个指针的距离保持在k-1,当第一个(走在前面的)指针到达链表的尾结点时,第二个指针(走在后面的)指针正好是倒数第k个结点。
下图展示了在有6个结点的链表上找倒数第3个结点的过程
public class Solution { public ListNode FindKthToTail(ListNode head,int k) { //遍历整个链表长度length,如果给出的k值大于length,那么直接出错 int length =0; ListNode head1 = head; while(head1!=null){ length++; head1 = head1.next; } if(k<=0 || k>length) return null; //找到链表的第一个和第二个指针,分别为ahead和behind ListNode ahead = head; ListNode behind =head;; //将ahead的位置移到k-1 位置,此时链表起始位为behind for(int i=0;i
转载地址:http://ezugn.baihongyu.com/