15.チェーンテーブルの最後からk番目のノード(JAVA)
7265 ワード
チェーンテーブルの最後からk番目のノード
タイトルの説明
チェーンテーブルを入力し、チェーンテーブルの最後からk番目のノードを出力します.
具体的な実装
解法1:
**解題の考え方:**まず統計の総結点数countを遍歴して、2種類の情況に分けます 1.k>countの場合null に直接戻ります. 2.k
解法2:
**解題の考え方:**この解法は前の解法よりずっとよくて、この解法はチェーンテーブルを1回遍歴するだけで、しかもこの解法も不法な出力を処理しました. 1.入力されたチェーンテーブルがnullまたはk=0(k=0は意味がない)であれば、nullを直接返します. 2.チェーンテーブルのノード数がk個未満の場合もnullを返します. 3.2つのポインタp 1=head、p 2=headを確立し、p 1はk-1ステップ(このときp 1.next!=nullである場合、総括点数がk以上であることを示す)、 そしてp 1とp 2は同時に、p 1が末尾、すなわちp 1まで進む.next==null,このときp 2は逆数k番目のノード(p 2-p 1+1であるk個のノードのため) である.
タイトルの説明
チェーンテーブルを入力し、チェーンテーブルの最後からk番目のノードを出力します.
具体的な実装
解法1:
**解題の考え方:**まず統計の総結点数countを遍歴して、2種類の情況に分けます
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null)
return head;
int count = 1;
ListNode temp = head;
while(temp.next != null) {//
count++;
temp = temp.next;
}
if(count < k)// k null
return null;
for(int i = 0;i < count-k; i++) {// count-k
head = head.next;
}
return head;
}
}
解法2:
**解題の考え方:**この解法は前の解法よりずっとよくて、この解法はチェーンテーブルを1回遍歴するだけで、しかもこの解法も不法な出力を処理しました.
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k == 0)// k=0 null
return null;
ListNode p1 = head, p2 = null;
for(int i = 0; i < k - 1; ++i) {//p1 k-1
if(p1.next != null)
p1 = p1.next;
else { // k-1 ， ， null
return null;
}
}
p2 = head;
while(p1.next != null) {//p1、p2 ， p1 ，p2 k 。
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
}