链表中倒数第k个结点

xiaoxiao2021-03-01  20

题目描述

输入一个链表,输出该链表中倒数第k个结点。

代码实现

# -*- 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 #最笨的方法,先找到最后一个节点,计算节点个数,找到倒数第k个节点的正数位置 p = head i = 0 while p: i += 1 p = p.next #返回len-k个位置的节点(从0开始计数时) j = 1 if i<k: return None while j<=i-k: j += 1 head = head.next return head ''' #使用两个指针,相隔k步 left = right = head for i in range(k): if right==None: return None right = right.next while right: right = right.next left = left.next return left '''

思路

两种思路,一种比较笨的方法,一种相对巧得办法。

第一种:通过第一次遍历整个链表,得到所有节点得个数,比如有5个结点,1->2->3->4->5,返回倒数第二个结点,就是4,他所在的正数位置是第(5-2=3)个位置(从0开始计数)。在第二次遍历的时候在遍历到第3个位置就停止,直接输出即可。

第二种:通过设置两个指针分别指向两个位置序号相差k的节点,其实中间相隔k-1个节点。然后二者同步向后移动,直到最右侧的指针所指节点移到尾节点的下一节点,即所指为空时,左侧指针所指即为倒数第k个节点。

 

转载请注明原文地址: https://www.6miu.com/read-4200202.html

最新回复(0)