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

zltzlt

来源于 CSDN

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

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

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

class Solution:
    def FindKthToTail(self, head, k):
        n = 0
        p = head
        while p is not None:
            n += 1
            p = p.next
        if n < k:
            return None
        p = head
        m = 1
        while m < (n - k + 1):
            m += 1
            p = p.next
        return p

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

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

class Solution:
    def Merge(self, pHead1, pHead2):
        if pHead1 is None:
            return pHead2
        if pHead2 is None:
            return pHead1

        if pHead1.val <= pHead2.val:
            pHead1.next = Solution.Merge(self, pHead1.next, pHead2)
            return pHead1
        else:
            pHead2.next = Solution.Merge(self, pHead1, pHead2.next)
            return pHead2

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

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