专栏首页Bingo的深度学习杂货店Leetcode【86、92、148、206】

Leetcode【86、92、148、206】

问题描述:【Linked List】86. Partition List
解题思路:

这道题是给一个链表和整数 x,将小于 x 的数按位置顺序放在链表左侧,大于等于 x 的按位置顺序放在右侧。

类似于快排的划分过程有木有。可以建立两个指针 l_end 和 r_end,分别指向 x 的左右两部分的尾部。再建立一个指针指向当前结点 cur,便于链表的遍历。因为我们不知道第一个结点和 x 的关系,所以可以建一个空结点 node 指向 head,最后 head.next 就是答案。

  • l_end 初始化为 head(空结点),r_end 初始化为 None,cur 指向 head.next 第一个结点;
  • 遍历 cur: 1、如果 cur.val < x and r_end == None,说明刚开始碰到的都是小于 x 的,就只需要移动 l_end 到 cur 的位置即可; 2、 如果 cur.val < x,这个时候 r_end 不为空,利用这三个指针进行交换和移动即可; 3、否则,碰到的都是大于等于 x 的,就只需要移动 r_end 到 cur 的位置即可。

时间复杂度为 O(n),空间复杂度为 O(1)。

Python3 实现:
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        node = ListNode(-1)  # 头结点
        node.next = head
        head = node
        l_end, r_end, cur = head, None, head.next
        while cur:
            if cur.val < x and r_end == None:  # 没遇到比 x 大的,只移动 l_end
                l_end = cur
            elif cur.val < x:  # r_end 不为 None,利用三指针交换
                r_end.next = cur.next  # 交换
                cur.next = l_end.next
                l_end.next = cur
                l_end = cur  # 移动
                cur = r_end
            else:
                r_end = cur
            cur = cur.next
        return head.next

问题描述:【Linked List】92. Reverse Linked List II
解题思路:

这道题是给一个链表和区间 [m, n],反转区间内的数字。

这道题和下面的 Leetcode 206 思路相同。对于一个区间的反转,需要用 notr 记录不用反转区间的最后一个位置;用 start 记录反转区间的头指针;为了反转方便,再定义 pre 和 cur 分别为前一个指针和当前指针。遍历 cur,找到反转区间,进行指针的交换和移动操作即可。

时间复杂度为 O(n),空间复杂度为 O(1)。

Python3 实现:
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if not head:
            return head
        # notr: 不用反转区间的最后一个位置
        # start: 反转区间的头指针
        # pre, cur:前一个指针和当前指针
        notr, start, pre, cur = None, None, None, head
        i = 1
        while cur:
            if i <= m:
                if i == m:  # 初始化四个指针
                    notr = pre
                    start = cur
                pre = cur
                cur = cur.next
            elif m < i <= n:  # 在起始位置的下一个位置反转,通过指针交换完成
                pre.next = cur.next # 交换
                cur.next = start
                start = cur
                if m == 1:  # 从头开始
                    head = cur
                else:  # 从中间开始
                    notr.next = start
                cur = pre.next  # 移动
            else:
                break
            i += 1
        return head

问题描述:【Linked List】148. Sort List
解题思路:

这道题是给一个链表,对链表排序。要求时间复杂度 O(nlogn),空间复杂度 O(1)。

首先,肯定能想到要么是使用快速排序,要么是归并排序。刚好上面的 Leetcode 86 为链表划分,所以就借助其思想实现了快排。但是最后一个 case 超时了(嘤嘤嘤),代码如下:

Python3 实现:
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:  # 递归出口
            return head
        pivot = head.val
        le, ri, cur = head, None, head.next  # 左右区间划分
        while cur:
            if cur.val < pivot and ri == None:
                le = cur
            elif cur.val < pivot:
                ri.next = cur.next  # 交换
                cur.next = le.next
                le.next = cur
                le = cur  # 移动
                cur = ri
            else:
                ri = cur
            cur = cur.next
        ri = le.next  # 左右两侧排序
        le.next = None
        lp = self.sortList(head.next)
        rp = self.sortList(ri)
        if lp == None:   # 将基准 head.val 放到中间
            head.next = rp
            lp = head
        else:
            cur = lp
            while cur.next:
                cur = cur.next
            cur.next = head
            head.next = rp
        return lp  # 返回链表头结点

看了题解,有人使用归并排序 mergeSort 通过了,同样可以做到时间复杂度为 O(nlogn),空间复杂度为 O(1)。代码如下(不是我写的,懒得再写一次了):

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if head is None:
            return None
        p, i = head, 0
        while p:
            i += 1
            p = p.next
        return self.mergeSort(head, i)[0]
            
    def mergeSort(self,head,k):
        if k == 1:
            next = head.next
            head.next = None
            return head, next
        left_head, next = self.mergeSort(head, k//2)
        right_head, next = self.mergeSort(next, k-(k//2))
        return self.merge(left_head, right_head), next

    def merge(self, h1, h2):
        dummy = ListNode(0)
        p = dummy
        while h1 and h2:
            if h1.val <= h2.val:
                p.next = h1
                p = p.next
                h1 = h1.next
            else:
                p.next = h2
                p = p.next
                h2 = h2.next
        if h1 is None and h2 is not None:
            p.next = h2
        elif h2 is None and h1 is not None:
            p.next = h1
        return dummy.next

问题描述:【Linked List】206. Reverse Linked List
解题思路:

这道题是给一个链表,将链表反转。

链表反转只需要两个相邻指针 pre 和 cur 即可。对于 cur 遍历,先交换(3 次操作)后移动指针到正确的位置,时间复杂度为 O(n)。

Python3 实现:
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        pre, cur = head, head.next
        while cur:
            pre.next = cur.next  # 交换
            cur.next = head
            head = cur
            cur = pre.next  # 移动
        return head

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 分类刷题 —— Linked List

    最近有朋友问我怎么没有更新文章了,因为最近有空的时候都在刷 LeetCode,零零星星刷了快 2 个月了,也累积了不少题目了,所以最近打算把做的几百道题归类,总...

    一缕殇流化隐半边冰霜
  • AVFrame转换到Mat,yuv420p转换到RGB源代码

    FFmpeg中AVFrame到OpenCV中Mat的两种转换方法 方法一:查表法 void AVFrame2Img(AVFrame *pFrame, cv::M...

    一棹烟波
  • 工具推荐:BadAssMacros免杀宏生成器

    在众多的攻击方式中,钓鱼文档攻击仍然扮演者重要的地位,而随着各类安全防护设备的成熟,宏免杀一直是我们所讨论的问题,之前有MacroPack(收费版仍然好...

    鸿鹄实验室
  • asp企业网站源码部分

    用户1112962
  • 带新手玩转MVC——不讲道理就是干(上)

    前言:这几天更新了几篇博客,都是关于Servlet、JSP的理解,后来又写了两种Web开发模式,发现阅读量还可以,说明JSP还是受关注的,之前有朋友评论说JSP...

    泰斗贤若如
  • 【旧代码】传热过程数值模拟

    byronhe
  • 1000个常用的Python库和示例代码

    下面是programcreek通过分析大量开源代码,提取出的最常用的python库。

    用户4962466
  • 商城项目回顾整理(一)前台页面布局

    登录页面: 1 <%@ page language="java" contentType="text/html; charset=utf-8" 2 ...

    二十三年蝉
  • 图片缩放+拖动(html)

    冰封一夏
  • Web网页安全色谱

    本文由来源 21aspnet,由 javajgs_com 整理编辑,其版权均为 21aspnet 所有,文章内容系作者个人观点,不代表 Java架构师...

    Java架构师必看
  • (七十)c#Winform自定义控件-饼状图

    GitHub:https://github.com/kwwwvagaa/NetWinformControl

    冰封一夏
  • Node.js爬虫数据抓取乱码问题总结

    所有这里主要说的是 Windows-1251(cp1251)编码与utf-8编码的问题,其他的如 gbk就先不考虑在内了~

    书童小二
  • (三十一)c#Winform自定义控件-文本框(四)

    GitHub:https://github.com/kwwwvagaa/NetWinformControl

    冰封一夏
  • c#贪吃蛇

    4、方向键控制蛇的移动方向,蛇不可反方向移动,如正在向上移动,不能马上向下,只能向左、右、上运动

    冰封一夏
  • 图书展示案例css版本

    黑泽君
  • Software caused connection abort: socket write...

    严重: Servlet.service() for servlet default threw exception java.net.Socke...

    闵开慧
  • mybatis3.2.8 与 hibernate4.3.6 混用

    mybatis、hibernate这二个框架各有特色,对于复杂的查询,利用mybatis直接手写sql控制起来更灵活,而一般的insert/update,hib...

    菩提树下的杨过
  • (二十八)c#Winform自定义控件-文本框(一)

    GitHub:https://github.com/kwwwvagaa/NetWinformControl

    冰封一夏
  • (九)c#Winform自定义控件-树

    GitHub:https://github.com/kwwwvagaa/NetWinformControl

    冰封一夏

扫码关注云+社区

领取腾讯云代金券