《剑指offer》---输出链表倒数第k个结点

本文算法使用python3实现


1 题目描述:

  输入一个链表,输出该链表中倒数第k个结点。
  时间限制:1s;空间限制:32768K


2 思路描述:

  方法一:当链表长度为 $ n $ 时,输出链表倒数第 $ k $ 个节点,即输出链表正数第 $ n-k $ 个节点。需先遍历链表计算链表长度,再从头至尾查找第 $ n-k $ 个节点,并输出。
  方法二:可以用两个指针同时指向链表头结点,第一个指针先遍历到第k个结点,此时第二个指针指向头结点,两个指针的距离为k-1。从此时起,同时后移第一个指针和第二个指针,直到第一个指针的next==None,即第一个指针指向最后一个节点的时候,第二个指针所指向的节点,就是倒数第k个结点。
   注意:两种方法中都需要先判断k值是否小于零或者链表是否为空,此时若是,应返回None;其次第一个指针移向第k个节点的过程中,若循环提前退出,说明链表长度小于k,应返回None


3 程序代码:

(1)方法一

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
	def FindKthToTail(self, head, k):
		'''统计链表个数,输出第n-k个(注意是返回节点,不是返回节点的值)'''
		# 链表为空或k小于0
		if head == None or k <= 0:
			return None
		p = head
		lens = 0
		while p!= None:
			lens += 1
			p = p.next
		# k值大于链表长度
		if k > lens:
			return None
		i = 0
		q = head
		while i < lens-k:
			q = q.next
			i += 1
		return q



(2)方法二:

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
	def FindKthToTail(self, head, k):
		'''	可以用两个指针,一个指针遍历到第k个结点的时候,第二个指针再走到第一个节点,
			然后两个指针的距离始终保持k-1,这样,当第一个指针的next==NULL,也就是走到最后一个节点的时候,
			第二个指针对应的位置,就是倒数第k个结点。'''
		if head == None or k <= 0:
			return None
		p1 = head
		p1Count = 1
		p2 = head
		while p1 != None and p1Count < k:
			p1 = p1.next
			p1Count += 1
		# 当k大于链表长度时
		if p1 == None:
			return None
		while p1.next != None:
			p1 = p1.next
			p2 = p2.next
		return p2 
原文地址:https://www.cnblogs.com/lliuye/p/9062817.html