更新：此题解 markdown 源文件已放到 Github https://github.com/bytetopia/offer-coding-interviews-python (opens new window)，欢迎前去给个小星星鸭！

---

链表中倒数第k个节点

问题

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

思路

1）先扫一遍链表，获得总个数n，然后从头走n-k+1次，就得到倒数第k个了。缺点是要扫两遍 2）两个指针从开头出发，第二个指针先往后走k-1步，然后两个指针同时往后走，当第二个到达末尾时，第一个指向的就是倒数第k个

需要注意 head为空、k小于或等于0时，k大于链表长度时的特殊情况 需留心不要写错边界条件

代码

class Solution:
    def FindKthToTail(self, head, k):
        if (not head) or k <= 0:
            return None
        count = 0
        pointer = head
        while(count < k and pointer):
            count += 1
            pointer = pointer.next
        if count < k:
            return None
        else:
            target = head
            while(pointer):
                target = target.next
                pointer = pointer.next
            return target

反转链表

问题

输入一个链表，反转链表后，输出链表的所有元素（函数返回头节点即可）。

分析

如下面所示，有三个指针，此时，让2的next指向1进行反转，然后指针2移动到3的位置，指针1移动到2的位置，指针3后移，继续进行反转，直到指针3指向为空时再进行最后一次反转。

需要特别注意的就是指针赋值的顺序有先后之分，不要弄丢了指针。

需注意代码鲁棒性，考虑到头节点指针为空、只有1个节点即头节点的两种特殊情况。

代码

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # 判断头节点为None或者只有头节点的特殊情况
        if not (pHead and pHead.next):
            return pHead
        a = pHead
        b = pHead.next
        # 需注意处理原来的头节点
        pHead.next = None
        while(b):
            c = b.next
            b.next = a
            a = b
            b = c
        return a

合并两个排序的链表

问题

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路

两个指针指向两个链表，比较当前两个数，把较小的连到结果链上，指针后移，直到其中某个链表走完，把另一链表余下部分连到结果链末尾即可。

需要注意处理特殊输入（空）的情况。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        h = ListNode(0)
        head = h
        p1, p2 = pHead1, pHead2
        while p1 and p2:
            if p1.val <= p2.val:
                h.next = p1 
                h = p1
                p1 = p1.next 
            else:
                h.next = p2
                h = p2
                p2 = p2.next 
        if p1:
            h.next = p1
        if p2:
            h.next = p2
        return head.next

注意由于是链表，所以最后将余下部分直接整个链上就行，不需要再去遍历余下的部分了 = =

树的子结构

题目

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路

首先遍历树1，找到树1中与树2根节点值相等的节点，说明可能就是子结构的根。 然后检查以此节点为根的树3，是否包含树2中的结构。特别注意是3包含2，因此应当遍历2，看2中的结构在3中是否都有，即使3比2多，若2的结构3都有的话，也是包含。

class Solution:
    def HasSubtree(self, pRoot1, pRoot2):   # 相当于这里做了一次递归的先序遍历，用来找p1中跟p2根结点相等的节点。
        result = False
        if pRoot1 and pRoot2:
            if pRoot1.val == pRoot2.val:
                result = self.check_structure(pRoot1, pRoot2)
            if not result:
                result = self.HasSubtree(pRoot1.left, pRoot2) # 需注意这里是 HasSubtree
            if not result:
                result = self.HasSubtree(pRoot1.right, pRoot2)
        return result
        
    def check_structure(self, root1, root2):  # 这里又是一种递归的先序遍历，用来判断两棵子树是否是root1包含了root2
        if not root2:
            return True
        if not root1:
            return False
        if root1.val != root2.val:
            return False
        left_check = self.check_structure(root1.left, root2.left)
        right_check = self.check_structure(root1.right, root2.right)
        return left_check and right_check