乐趣区

关于python:剑指offer详解链表python

jiezi

3. 从尾到头打印链表 

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回从尾部到头部的列表值序列，例如 [1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        if not listNode:
            return []
        l=[]
        while listNode:
            l.append(listNode.val)
            listNode=listNode.next
        return l[::-1]

14. 链表中倒数第 k 个结点 

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if not head or k<=0: return None
        p=q=head
        t=0
        while p and t < k: # 将两个指针隔开 k 的间隔
            p=p.next
            t+=1
        if t<k: return None # 如果倒数的个数大于链表个数则返回空
        while p!=None: # 否则将从头的链表挪动到曾经挪动的链表挪动到结尾为止
            q=q.next
            p=p.next
        return q

15. 反转链表

同时也是 206. 反转链表（leetcode）
反转一个单链表。
示例:
输出: 1->2->3->4->5->NULL
输入: 5->4->3->2->1->NULL
迭代解法：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur, pre = head, None
        while cur:
            temp=cur.next # 保留原链表后续的内容，不让链表断掉。temp 就是原链表从第二个节点开始的一个链表
            cur.next=pre #把 cur 的指针间接指向 pre
            pre=cur # 替换这个革新后的 pre
            cur=temp # 替换这个革新后的 cur
        return pre

16. 合并两个排序的链表 

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1
        cur = ListNode(0)
        # while pHead1 and pHead2:
        if pHead1.val<= pHead2.val:
            cur=pHead1
            cur.next=self.Merge(pHead1.next, pHead2)
        else :
            cur=pHead2
            cur.next=self.Merge(pHead1, pHead2.next)
        return cur

25. 简单链表的复制

用递归去做，会很简略，但这题可能不适宜 python

class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead: return None
        pCopy=RandomListNode(pHead.label) # 新建一个和 pHead 一样内容的 RandomListNode 对象
        pCopy.random=pHead.random # 一个 RandomListNode 须要指定的值就是 random 和 next
        # pCopy.next=pHead.next
        pCopy.next=self.Clone(pHead.next)
        return pCopy
退出移动版