输入一个链表,输出一个链表,该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。
如果该链表长度小于k,请返回一个长度为 0 的链表。
首先我们清楚,链表是由其头节点决定的,所以问题转化为输入一个头节点,输出一个头节点。所以我们只需要输出倒数第k个节点即可
方法1 常规一个循环解决
先求出链表长度,一个遍历就可以找到该节点。
时间复杂度 O(n)
空间复杂度 O(1)
import java.util.*; public class Solution { public ListNode FindKthToTail (ListNode pHead, int k) { // write code here if(pHead == null){ return null; } int length = 0; ListNode node = pHead; while(node.next != null){ node = node.next; length++; } if(k > length+1){ return null; } ListNode pre = pHead; for(int i=0; i<length-k+1; i++){ pre = pre.next; } return pre; } }
方法2 双指针法
用指针pre先移动k个节点,之后两个指针同时移动,当pre指针移到链表末尾时,ref指针刚好移动到倒数第k个节点,输出ref指针即可。
时间复杂度 O(n)
空间复杂度 O(1)
import java.util.*; public class Solution { public ListNode FindKthToTail (ListNode pHead, int k) { // write code here ListNode pre = pHead; ListNode ref = pHead; while(k>0){ if(pre == null){ return null; } pre = pre.next; k--; } while(pre != null){ pre = pre.next; ref = ref.next; } return ref; } }