題目描述
輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點跌榔。
知識點
鏈表
Qiang的思路V1
看到這個題最先想到的辦法就是遍歷一遍將所有的節(jié)點保存到一個列表中异雁，然后就能直接得到倒數(shù)第k個節(jié)點了。
# -*- 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
l=[]
while head!=None:
l.append(head)
head=head.next
if len(l)<k or k==0:
return None
return l[-k]
但是這種方法需要的空間復(fù)雜度為O(n)僧须，實在是太浪費空間了纲刀。
Qiang的思路V2
因為第一個思路太浪費空間，我就想肯定存在一種不需要額外空間的方法完成這個問題担平，然后就只能在鏈表身上動手腳了示绊。
所以我用了兩個指針，分別標(biāo)識當(dāng)前遍歷的位置和距離當(dāng)前位置的前k個位置暂论。所以只要我在遍歷的時候保持兩個指針同步移動面褐，那么當(dāng)?shù)谝粋€指針到達(dá)鏈表最后一個節(jié)點時，第二個指針恰恰是需要的節(jié)點取胎。
# -*- 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
p=head
for i in range(1,k):
if head.next==None:
return None
head=head.next
while head.next!=None:
head=head.next
p=p.next
return p
完美的代碼展哭，空間復(fù)雜度降了，也不用求長度了闻蛀，時間效率也提高了匪傍。
作者原創(chuàng)，如需轉(zhuǎn)載及其他問題請郵箱聯(lián)系：lwqiang_chn@163.com觉痛。
個人網(wǎng)站：https://www.myqiang.top役衡。
