10-27LeetCode刷题（三）

用户11029137

发布于 2024-10-31 08:12:30

690

发布于 2024-10-31 08:12:30

文章被收录于专栏：编程学习

LeetCode21

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1: return list2
        if not list2: return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next,list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1,list2.next)
            return list2

来自Leetcode上的讲解：关于return L1的个人理解: 递归的核心在于,我只关注我这一层要干什么,返回什么,至于我的下一层(规模减1),我不管,我就是甩手掌柜. 好,现在我要merge L1,L2.我要怎么做?

显然,如果L1空或L2空,我直接返回L1或L2就行,这很好理解. 如果L1第一个元素小于L2的? 那我得把L1的这个元素放到最前面,至于后面的那串长啥样 ,我不管. 我只要接过下级员工干完活后给我的包裹, 然后把我干的活附上去(令L1->next = 这个包裹)就行这个包裹是下级员工干的活,即merge(L1->next, L2) 我该返回啥?

现在不管我的下一层干了什么,又返回了什么给我, 我只要知道,假设我的工具人们都完成了任务, 那我的任务也就完成了,可以返回最终结果了最终结果就是我一开始接手的L1头结点+下级员工给我的大包裹,要一并交上去, 这样我的boss才能根据我给它的L1头节点往下找,检查我完成的工作

LeetCode328

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head: return head
        odd_list = head
        even_list = head.next
        even_head = even_list  #记录偶数列表的头结点
        while even_list and even_list.next:
            odd_list.next = even_list.next # 下一个奇数索引节点是当前偶数索引节点的下一个节点
            odd_list = odd_list.next # 奇数索引节点后移
            even_list.next = odd_list.next
            even_list = even_list.next
        odd_list.next = even_head # 把偶数链连接在奇数链后面
        return head

先分别得到奇数链和偶数链，最后再把偶数链连在奇数链的后面

LeetCode92

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        p0 = dummy = ListNode(next=head)
        for _ in range(left-1):
            p0 = p0.next
        pre = None
        cur = p0.next #p0是要逆转的部分的前一个节点
        for _ in range(right-left+1):
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt

        p0.next.next = cur
        p0.next = pre
        return dummy.next