チェーンテーブルの最後からk番目のノード[剣指offer]のpython実現
タイトルの説明
チェーンテーブルを入力し、チェーンテーブルの最後からk番目のノードを出力します.
タイトルリンク
解法1:主にkとチェーンテーブルの個数の大きさの関係を考慮して、2つのポインタで遍歴します
解法2:まず個数nを統計してからn-k+1を求める
解法2はもっと速い
チェーンテーブルを入力し、チェーンテーブルの最後からk番目のノードを出力します.
タイトルリンク
解法1:主にkとチェーンテーブルの個数の大きさの関係を考慮して、2つのポインタで遍歴します
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindKthToTail(self, head, k):
# write code here
if k<=0 or head==None:
return None
else:
count=0
p=head
mark=False
ans=head
while p!=None:
count=count+1
if count>k:
ans=ans.next
p=p.next
if countNone
return ans
解法2:まず個数nを統計してからn-k+1を求める
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindKthToTail(self, head, k):
# write code here
if k<=0 or head==None:
return None
count=0
p=head
while p!=None:
count=count+1
p=p.next
if countreturn None
number=count-k+1
cnt=0
p=head
while p!=None:
cnt=cnt+1
if cnt==number:
return p
p=p.next
解法2はもっと速い