链表

(1)链表的中间节点

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow=fast=head
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
        return slow

# 快慢指针

(2)合并两个有序链表

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: return l2
        if not l2: return l1
        if l1.val<l2.val:
            l1.next=self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next=self.mergeTwoLists(l1,l2.next)
            return l2

# 递归

(3)445.两数相加 II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        s1,s2=[],[]
        while l1:
            s1.append(l1.val)
            l1=l1.next
        while l2:
            s2.append(l2.val)
            l2=l2.next
        ans,carry=None,0

        while s1 or s2 or carry != 0:
            a = 0 if not s1 else s1.pop()
            b = 0 if not s2 else s2.pop()
            cur = a + b + carry
            cur,carry=cur%10,cur//10

            curnode = ListNode(cur)

            curnode.next = ans 
            ans = curnode           #头部接入
        return ans

# 栈，链表

(5)环形链表II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast,slow=head,head
        while True:
            if not fast or not fast.next: return 
            fast,slow=fast.next.next,slow.next
            if fast==slow: break
        fast=head
        while fast!=slow:
            fast,slow=fast.next,slow.next
        return fast

# 记f,s分别为快慢指针走过的节点。
# 记a,b分别为环外、环内节点数
# f=2s=s+nb，s=nb.
# 更换指向后：f'=a,s=nb+a,是重合的，在入口处。

(6)两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        newhead=head.next
        head.next=self.swapPairs(newhead.next)
        newhead.next=head
        return newhead

203. 移除链表元素

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode(0,head)
        p = dummy
        while p:
            while p.next and p.next.val == val:
                p.next = p.next.next
            p = p.next
        return dummy.next

21. 合并两个有序链表

1. 迭代

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        ans = ListNode(0)
        p = ans

        while l1 or l2:
            if not l2:
                p.next = ListNode(l1.val, None)
                l1 = l1.next
            elif not l1:
                p.next = ListNode(l2.val, None)
                l2 = l2.next
            elif l1.val<=l2.val:
                p.next = ListNode(l1.val, None)
                l1 = l1.next
            else:
                p.next = ListNode(l2.val, None)
                l2 = l2.next
            p = p.next

        return ans.next

2.递归

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: return l2
        if not l2: return l1
        if l1.val <= l2.val:
            l1.next = self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1,l2.next)
            return l2

141. 环形链表

给定一个链表，判断链表中是否有环。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if(not head or not head.next): return False
        slow, fast = head, head.next
        while slow != fast:
            if (not fast or not fast.next):
                return False
            slow = slow.next
            fast = fast.next.next
        return True

#快慢指针
# 1.slow放在head, fast放在head.next
# 2.while(slow!=fast)来移动指针

206. 反转链表

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre, cur = None, head
        while cur:
            cur.next, pre, cur = pre, cur, cur.next
        return pre

# pre 为返回的链表指针
# 这种赋值写法，不用写中间变量了

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

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        p = head
        while p and p.next:
            if p.val == p.next.val:
                p.next = p.next.next
            else:
                p = p.next
        return head