剑指Offer编程题(python)——链表

1、从尾到头打印链表

#输入一个链表，按链表值从尾到头的顺序返回一个arraylist。
class listnode:
    def __init__(self, x):
        self.val = x
        self.next = none

class solution:
    
    def printlistfromtailtohead(self, listnode):
        # write code here
        l = []
        head = listnode
        while head:
            l.insert(0, head.val) #插入
            head = head.next
        return l

2、链表中倒数第k个结点

#输入一个链表，输出该链表中倒数第k个结点。
class solution:
    def findkthtotail(self, head, k):
        # write code here
        l=[]
        while head!=none:
            l.append(head)
            head=head.next
        if k>len(l) or k<1:
            return
        return l[-k]

3、反转链表

#输入一个链表，反转链表后，输出新链表的表头。
class solution:
    # 返回listnode
    def reverselist(self, phead):
        # write code here
        l = []
        if phead == none:
            return
        while phead:
            l.insert(0,phead)
            phead = phead.next
        for i in range(len(l)-1):
            l[i].next = l[i+1]
        l[-1].next =none
        return l[0]

4、合并两个排序的链表

#输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
class solution:
    def merge(self,phead1,phead2):
        l1=[]
        l2=[]
        while phead1:
            l1.append(phead1)
            phead1 =phead1.next
        while phead2:
            l2.append(phead2)
            phead2 =phead2.next
        l =l1 +l2
        if l ==[]:
            return none
        for i in range(len(l)-1):
            for j in range(i+1,len(l)):
                if l[i].val>l[j].val:
                    l[i],l[j] = l[j],l[i]
        for t in range(len(l)-1):
            l[t].next= l[t+1]
        l[-1].next =none
        return l[0]

5、复制链表的复制

#输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），
#返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
class randomlistnode:

def __init__(self, x):
        self.label = x
        self.next = none
        self.random = none
class solution:
    # 返回 randomlistnode
    def clone(self, phead):
        # write code here
        if not phead:
            return none
        cur = phead
        while cur:
            tmp = randomlistnode(cur.label)
            tmp.next = cur.next
            cur.next = tmp
            cur = tmp.next
        cur = phead
        while cur:
            tmp = cur.next
            if cur.random:
                tmp.random = cur.random.next
            cur = tmp.next
        cur = phead
        res = phead.next
        while cur.next:
            tmp = cur.next
            cur.next = tmp.next
            cur = tmp
        return res 

6、二叉搜索树与双向链表

#输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
#要求不能创建任何新的结点，只能调整树中结点指针的指向。

class solution:
    def convert(self, prootoftree):
        # write code here
        if not prootoftree:return
        self.arr = []
        self.midtraversal(prootoftree)
        for i,v in enumerate(self.arr[:-1]):
            v.right = self.arr[i + 1]
            self.arr[i + 1].left = v
        return self.arr[0]
 
    def midtraversal(self, root):
        if not root: return
        self.midtraversal(root.left)
        self.arr.append(root)
        self.midtraversal(root.right)

7、两个链表的第一个公共结点

#输入两个链表，找出它们的第一个公共结点。
class solution:
    def findfirstcommonnode(self, phead1, phead2):
        # write code here
        l1 = []
        result= []
        while phead1:
            l1.append(phead1.val)
            phead1= phead1.next
        while phead2:
            if phead2.val in l1:
                result.append(phead2)
            phead2 = phead2.next
        if result == []:
            return none
        else:
            return result[0]

8、链表中环的入口结点

#给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
class solution:
    def entrynodeofloop(self, phead):
        # write code here
        l = []
        while phead:
            l.append(phead)
            phead = phead.next
            if phead in l:
                return phead

9、删除链表中重复的结点

#在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
#例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
#方法：先遍历,使得链表->列表，剔除列表中重复的元素，根据新列表重构链表
class solution:
    def deleteduplication(self, phead):
        vals = []
        nodes =[]
        while phead:
            vals.append(phead.val)
            nodes.append(phead)
            phead = phead.next
        vals = list(filter(lambda c: vals.count(c) == 1, vals))
        nodes = list(filter(lambda d: d.val in vals, nodes))
        if nodes== []:
            return none
        for i in range(len(nodes)-1):
            nodes[i].next = nodes[i+1]
        nodes[-1].next =none
        return nodes[0]