《剑指offer》python版本 分类刷题

链表

1. 从尾到头打印链表：借助列表模拟堆栈

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        if not listNode:
            return []
        stack = []
        p = listNode
        while p:
            stack.append(p.val)
            p = p.next
        return stack[::-1] # 列表反转，参考：https://www.runoob.com/note/51257

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

设置两个指针p和q，让q先走k-1步，然后两个指针一起走，等q走到了链表尾端，p所指的就是倒数第k个结点。

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if head == None or k<=0:
            return None
        p = head
        q = p
        while k-1:
            if q.next != None:
                q = q.next
                k = k - 1
            else:
                return None
        while q.next != None:
            p = p.next
            q = q.next
        return p

3. 链表反转

输入一个链表，反转链表后，输出新链表的表头。
[1,2,3,4]，q先置为Null，依次让1指向空，让2指向1，让3指向2…

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead == None or pHead.next == None:
            return pHead
        q = None
        while pHead.next != None:
            p = pHead
            pHead = pHead.next
            p.next = q 
            q = p 
        pHead.next = q
        return pHead

4. 合并两个排序的链表
   输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
   思路： 思路很简单，比较两个链表的值，谁大指向谁

class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        temp = ListNode(0) # 初始化一个链表
        res = temp
        while pHead1 and pHead2:
            if pHead1.val < pHead2.val:
                temp.next = pHead1
                pHead1 = pHead1.next
                temp = temp.next
            else:
                temp.next = pHead2
                pHead2 = pHead2.next
                temp = temp.next
        if pHead1:
            temp.next = pHead1
        if pHead2:
            temp.next = pHead2
        return res.next

5. 复杂链表的复杂

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

不会，跳过

6. 两个链表的第一个公共节点

啥是公共节点：

思路：

设两个链表长度差为k，先让长的那个走k步，再一起走，直到遇到相等节点。

class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        p1 = pHead1
        p2 = pHead2
        i = 0
        j = 0
        while p1:
            p1 = p1.next
            i = i + 1
        while p2:
            p2 = p2.next
            j = j + 1
            
        if i > j:
            while i-j:
                pHead1 = pHead1.next
                j = j + 1
        else:
            while j-i:
                pHead2 = pHead2.next
                i = i + 1
                
        while pHead1 and pHead2:
            if pHead1 == pHead2:
                return pHead1
            pHead1 = pHead1.next
            pHead2 = pHead2.next
        return None

本文地址：https://blog.csdn.net/weixin_42517469/article/details/107244912