leetcode 中的链表简单题 python3_python3 listnode

目录：

基本使用 //

21题 合并有序链表 //

83题 删除有序链表重复元素 //

141题 环形链表 //

160题 相交链表 //

203题 移除链表元素//

206题 反转链表 //

基本使用：

之前没有学过链表，leetcode最近在做简单题，才发现链表的定义，元素之间是通过节点连接的。链表类定义以后的函数调用解释：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
 
p = ListNode()
l1: ListNode 
#l1 就是链表里的指针所在的位置以及之后的元素
 
#若此链表为[1, 2, 3] 
#l1 = [1, 2, 3]
#l1.next = [2, 3]
l1.val #默认第0个元素 例子中为1
 
l1 = l1.next #指针后移
#此时l1.val 为2
#l1.next = [3]
 
 
p.next = ListNode(l1.val) #这个元素值赋给链表p的下一个元素

21题 合并有序链表

将两个有序链表合并为一个新的升序链表

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        p = ListNode()
        ans = p
        while l1 and l2:
            if l1.val < l2.val:
                p.next = ListNode(l1.val)
                l1 = l1.next
            else:
                p.next = ListNode(l2.val)
                l2 = l2.next
            p = p.next
        if l1:
            p.next = l1
        else:
            p.next = l2
        return ans.next
# p.next不被直接返回是因为p此时指针已经到了最后一个元素
#而提前设置的ans和p指向同一个链表，那么使用ans.next返回整个链表

83题 删除排序链表中的重复元素

1. 设置prev, cur = head, head.next, prev与head指向同一个链表 ;

2. perv.val == cur.val 时 prev跳过下一个值(cur.val) 直接保存next为cur.next 即 prev.next = cur.next ;  （指到后继节点的后继节点来删除本身的后继节点）

3. 若非如此，prev后移一个即 prev = cur. ;

4. 无论如何，cur = cur.next 后移往前进着

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return head
        perv, cur = head, head.next
        while cur:
            if perv.val == cur.val:
                perv.next = cur.next
            else:
                perv = cur
            cur = cur.next
        return head

141题 环形链表

看了某站up的讲解，才知道环形链表的意思...

环形通常出现在有循环处，那么一般就可用这两种常见办法。同类题型可见202题 快乐数。

方法一： 又顺便学了哈希表，哈希表在python里就是dict和set. dict相当于保存2个list，一个元素本身 一个下标（映射）。set保存1个list，元素本身。这个题可以使用哈希表存储，环形链表的环会存在于已建立的哈希表内，因此True条件为：node in s

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head: return False
        s = set()
        node = head
        while node:
            if node in s:
                return True
            else:
                s.add(node)
            node = node.next
        return False

方法二：快慢指针。还是很好理解的

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head: return False
        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next 
            #总是快一步，那么进入循环后总会在第二圈赶上slow，即相等
            if slow == fast:
                return True
        return False

160题 相交链表

方法一：用哈希表存储headA的所有后续节点，遍历headB，若遍历到指针存在于此哈希表，则说明存在。（这个是自己想出来的～）

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        s = set()
        nodeA = headA
        nodeB = headB
        while nodeA:
            s.add(nodeA)
            nodeA = nodeA.next
        while nodeB:
            if nodeB in s:
                return nodeB
            nodeB = nodeB.next
        return None

方法二：双指针。（来源用户 Krahets 题解）假设headA有a个节点，headB有b个节点，相交于c节点，设置2个指针：指针A从headA开始遍历，结束后遍历B至节点处需要走 (a+b-c) 个节点；指针B从headB开始遍历，结束后遍历A至节点处需要走 (b+a-c) 个节点，指针会相遇。返回此时指针A，若不相遇则A会遍历完 a+b 所有节点指向null. 时间复杂度O(a+b), 空间复杂度O(1) 常数大小的额外空间。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        A, B = headA, headB
        while A != B:
            A = A.next if A else headB 
            #若headA遍历完成则A=headB开始遍历
            B = B.next if B else headA
        return A

看到评论有人问为什么 A = A.next if A else A = headB 会报错，因为A = 赋值+赋值条件，后面是一个模块，等于语句 if A: A = A.next else: A = headB.  ifelse语句在赋值使用当然不需要再加赋值号啦...

203题 移除链表元素

思路很简单，保证第一个节点满足要求，然后进入判断循环，如果后继节点等于val就跳过后继节点赋值给next，否则直接指针后移。注意一点在保证头节点满足要求之后