1 算法 1 常规解法
2 算法 2 dfs 后续遍历
3 栈来模拟
算法1
(常规解法) O(n)
java代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode findKthToTail(ListNode pListHead, int k) {
int len = 0;
ListNode cur = pListHead;
while(cur!=null){
cur = cur.next;
len++;
}
int idx = 1;
cur = pListHead;
ListNode ans = null;
while(cur!=null){
if(idx==len-k+1){
ans = new ListNode(cur.val);
}
cur = cur.next;
idx++;
}
return ans;
}
}
算法2
(dfs后续遍历) O(n)
java 代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
private ListNode ans;
private int n;
private int mk;
public ListNode findKthToTail(ListNode pListHead, int k) {
mk = k;
dfs(pListHead);
return ans;
}
private void dfs(ListNode node){
if(node==null){
return;
}
dfs(node.next);
n++;
if(n==mk){
ans = new ListNode(node.val);
}
}
}
算法3
(栈实现) O(n)
用栈来模拟后续遍历,回溯的过程
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode findKthToTail(ListNode pListHead, int k) {
Stack<Integer> stack = new Stack<>();
ListNode cur = pListHead;
while(cur!=null){
stack.push(cur.val);
cur = cur.next;
}
int idx = 0;
ListNode ans = null;
while(!stack.isEmpty() && idx<k){
int v = stack.pop();
idx++;
if(idx==k){
ans = new ListNode(v);
}
}
return ans;
}
}