輸入一個鏈表，輸出該鏈表中倒數第 k 個結點
解法一
使用一個 ArrayList 保存鏈表的所有結點，然后再直接取出目標結點
import java.util.List;
import java.util.ArrayList;
public class Solution {
private List<ListNode> list = new ArrayList<>();
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || head.next == null ||k <= 0) {
return null;
}
while(head != null) {
list.add(head);
head = head.next;
}
if(k > list.size()) {
return null;
}
return list.get(list.size() - k);
}
}
解法二
使用雙指標的方式，指標 p 和 q 都先指向開始的節點，p 一直向后走，而 q 等到 p 走了 k 步再開始向后走，從這個時刻起 p 總是領先 q k 個位置，當 p 走到終點時，q 走到了倒數第 k 個節點
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null ||k <= 0) {
return null;
}
int count = 0;
ListNode p = head, q = head;
while(p != null) {
if(count >= k) {
q = q.next;
}
p = p.next;
count++;
}
return k > count ? null : q;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/140491.html
標籤：其他
上一篇：調整陣列順序使奇數位于偶數前面