文引

python面向对象，本人是java的，对于python理解欠佳，为朋友写此文。
链表node，包括它的值val，还有一个next指针指向下一个node
python的属性域都是在init里面定义的，私有属性用两个下划线开头
由于视频面试手撕代码，要自己定义输入数据，自己构造了相交链表
在本文的链表中，通过一个list来构造链表，由于是链表相交问题，又写一个链表拼接方法
注意面向对象，方法是一个对象的，函数则是某个功能(面向过程)

链表相交就是两个链表汇聚，一般不认为是一个链表的尾部和另一个链表的头部相交
链表相交有三种方法：

  • hash查找，遍历一个链表，放入hash表，然后查找。在python中 in应该算是一个方法，在不同数据结构中，复杂度不同
    • item in list 这需要遍历
    • item in set ,item in dict 这是o(1)。
  • stack 栈，两个链表压栈，然后出栈，python没有stack,只有list,通过list[len[list]-1]来实现top和peek方法。
  • 求链表长度，做差，长链表先走，让两个链表同步剩余长度后，开始同步走。当结点相同，说明到达了相交点。

代码

# 链表结点
class Node:
    def __init__(self, next, val=0):
        self.next = next
        self.val = val


# 链表
class LinkedList:
    def __init__(self, head: Node):
        self.head = head

    # 通过list构造链表
    def gen(self, linkedlist: list):
        h = Node(0)
        p = h
        for i in range(0, len(linkedlist), 1):
            p.next = Node(None, val=linkedlist[i])
            p = p.next
        self.head = h.next

    # 链表拼接
    def addList(self, link):
        if (link.__class__ is not LinkedList):
            return
        p = self.head
        while (p != None and p.next != None):
            p = p.next
        p.next = link.head

    def print(self):
        p = self.head
        while (p is not None):
            print(p.val, end=' ')
            p = p.next
        print()


# 堆栈法求链表相交结点
def getCom(l1: Node, l2: Node) -> Node:
    stack1 = []
    stack2 = []
    while (l1 is not None):
        stack1.append(l1)
        l1 = l1.next

    while (l2 is not None):
        stack2.append(l2)
        l2 = l2.next

    p = None
    while (stack1[len(stack1) - 1] is stack2[len(stack2) - 1]):
        p = stack1.pop()
        stack2.pop()
    return p


# 两次遍历求链表相交结点,作差法
def getCom2(l1: Node, l2: Node) -> Node:
    p1, p2 = l1, l2
    len1, len2 = 0, 0

    while (p1 != None):
        p1 = p1.next
        len1 += 1
    while (p2 != None):
        p2 = p2.next
        len2 += 1
    if (len1 < len2):
        p1, p2 = l2, l1
    else:
        p1, p2 = l1, l2

    ablen = abs(len1 - len2)
    for i in range(ablen):
        p1 = p1.next

    while (p1 is not p2):
        p1 = p1.next
        p2 = p2.next
    return p1

# hash查找
def getCom3(l1, l2) -> Node:
    hashmap = set() #o(1)查询 list是o(2)查询
    p1, p2 = l1, l2
    while (p1 is not None):
        hashmap.add(p1)
        p1 = p1.next
    while (p2 not in hashmap):
        p2 = p2.next
    return p2


if __name__ == "__main__":
    # 链表初始化
    linkedList1 = LinkedList(None)
    # 通过list构造链表
    linkedList1.gen([1, 2, 3, 4])

    linkedList2 = LinkedList(None)
    linkedList2.gen([5, 6])
    comLink = LinkedList(None)
    comLink.gen([7, 8, 9])
    # 链表拼接
    linkedList1.addList(comLink)
    linkedList2.addList(comLink)
    # 链表打印
    linkedList1.print()
    linkedList2.print()

    ## 两个链表相交
    print(getCom(linkedList1.head, linkedList2.head).val)
    print(getCom2(linkedList1.head, linkedList2.head).val)
    print(getCom3(linkedList1.head, linkedList2.head).val)