1、快慢指针:时间复杂度是O(n),空间复杂度O(1)
思路:快指针比慢指针多走K步,当快指针走完时,慢指针正好是倒数第K个
public ListNode FindKthToTail (ListNode pHead, int k) { if(pHead==null){ return null; } ListNode slow = pHead; ListNode fast = pHead; while(fast!=null&&k>0){ fast=fast.next; k--; } if(k>0){ return null; } while(fast!=null){ slow=slow.next; fast=fast.next; } return slow; }
2、统计链表长度:时间复杂度是O(n),空间复杂度O(1)
思路:通过统计链表的长度,计算倒数第K个是正数第几个,遍历链表到当前位置停下来。
public ListNode FindKthToTail (ListNode pHead, int k) { // write code here int s = 0; //统计链表长度 ListNode node = pHead; while(node!=null){ node=node.next; s++; } if(s<k){ return null; } //计算是第几个停下来 int target = s-k; s=0; while(s<target){ pHead = pHead.next; s++; } return pHead; }