｜ 返回鏈表中倒數第K個節點

輸入一個鏈表，輸出該鏈表中倒數第k個節點。為了符合大多數人的習慣，本題從1開始計數，即鏈表的尾節點是倒數第1個節點。

例如，一個鏈表有 6 個節點，從頭節點開始，它們的值依次是 1、2、3、4、5、6。這個鏈表的倒數第 3 個節點是值為 4 的節點。

示例：

給定一個鏈表: 1->2->3->4->5, 和 k = 2.

返回鏈表 4->5.

｜題解

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:"""提供三種解題思路:解題思路一: 1.先翻轉整個鏈表2.遍歷翻轉后的鏈表,用count來記錄位置, 然后用頭插法繼續翻轉即可解題思路二:1.找規律可得,倒數第k個元素就是正數n-k+1個元素2.先遍歷計算鏈表的長度，再遍歷到第n-k+1的位置即可解題思路三:1.快慢指針解法，先讓fast指針走k步2.當fast指針走k步后，fast指針和slow指針同步向后走，fast為None，slow就是倒數第k個位置"""def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:# 解法一cur = head# 反轉初始鏈表new_head = self.reserves(cur)new_head2 = Nonecount = 0while new_head:if count == k:breakelse:# 用頭插法反轉部分鏈表pre = new_head.nextnew_head.next = new_head2new_head2 = new_headnew_head = precount += 1return new_head2def reserves(self, head):new_head = Nonecur = headwhile cur:per = cur.nextcur.next = new_headnew_head = curcur = perreturn new_head# 解法二# 定義頭指針，添加虛擬頭節點new_head = Nonenode = ListNode()new_head = nodetail = node# 計算鏈表的長度count = 0cur = headwhile cur:count += 1cur = cur.next# s 為正向鏈表的位置s = count - k + 1count_1 = 0while head:if count_1 == s:breakelse:tail.next = headhead = head.nextcount_1 += 1return new_head.next#解法三fast = headslow = headcount = 0cur = headwhile fast:if count >= k:slow = slow.nextfast = fast.nextcount += 1return slow 《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的python 链表中倒数第k个节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。