Python 数据结构之链表 —— （二）倒数第 k 结点及链表合并

zltzlt

来源于 CSDN

Python 数据结构之链表 —— （二）倒数第 k 结点及链表合并

在熟悉了链表的基本操作以后，做一些网上各种的题目，巩固所学知识~

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

1. class Solution:
   
2.     def FindKthToTail(self, head, k):
   
3.         n = 0
   
4.         p = head
   
5.         while p is not None:
   
6.             n += 1
   
7.             p = p.next
   
8.         if n < k:
   
9.             return None
   
10.         p = head
    
11.         m = 1
    
12.         while m < (n - k + 1):
    
13.             m += 1
    
14.             p = p.next
    
15.         return p

复制代码

解析：链表无法回溯，不能从后向前，遍历一遍得到长度，再从头向后找即可。

2) 输入两个单调递增的链表，输出两个链表合成后的链表，合成后的链表需满足单调不减规则。

1. class Solution:
   
2.     def Merge(self, pHead1, pHead2):
   
3.         if pHead1 is None:
   
4.             return pHead2
   
5.         if pHead2 is None:
   
6.             return pHead1
   
7. 
   
8.         if pHead1.val <= pHead2.val:
   
9.             pHead1.next = Solution.Merge(self, pHead1.next, pHead2)
   
10.             return pHead1
    
11.         else:
    
12.             pHead2.next = Solution.Merge(self, pHead1, pHead2.next)
    
13.             return pHead2

复制代码

解析：参考了其他人的递归思路，使得代码十分简洁、诡异。

循环也可实现，但是有必要多熟悉递归的思想解决复杂的问题；链表问题除了链表头、尾特殊以外，剩下的部分用递归可解决，建议多用，领会这一算法思想。