本站消息

站长简介/公众号


站长简介:逗比程序员,理工宅男,前每日优鲜python全栈开发工程师,利用周末时间开发出本站,欢迎关注我的微信公众号:幽默盒子,一个专注于搞笑,分享快乐的公众号

  价值13000svip视频教程,python大神匠心打造,零基础python开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2020-07(10)

2020-08(50)

LeetCode 143: Reorder List 题解(python)

发布于2020-07-20 19:33     阅读(501)     评论(0)     点赞(25)     收藏(3)



Leetcode 143: Reorder List

分类:Linked List
难度:M (M+?)
描述:给了一个linkedlist,要按照一定的顺序把它重新排序。排序方法见示例。注意要求的是不可以改变每个节点的值,而是以节点为单位进行操作。没有返回值。
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

Given 1->2->3->4, reorder it to 1->4->2->3.

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

链接: Reorder List.

思路:

这个题咋一看很麻烦,其实思路上比较简单。首先,先找到这个链表的1/2处节点,然后前1/2节点不变,后1/2的链表反转,然后再把前后链表交替链接,即可得出结果。

首先,需要得到1/2处节点,可以使用快慢指针法,也可以用一个i去记录原始链表的长度,再去寻找1/2处的节点即可。此处将使用快慢指针法。

这个题麻烦在细节处理要细致一些,不然就会容易出错。因为没有返回值,而是在原链表上进行操作,所以需要仔细小心。还有别的细节上的问题,比方说在python中的linked list的表述,要明白以节点为代表的linkedlist,代表的是哪一部分,在什么地方指向None,每次复制linked list后,是对原始的linked list进行操作,还是对复制后的进行操作。这些需要多加注意。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head or not head.next:
            return None
        fast, slow = head, head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next   快慢指针法找到1/2处的节点
        head2 = slow.next      把后半部分的链表先复制出来,设置给head2
        slow.next = None       把前半段的尾节点指向None。
        curr = head2
        prev, nxt = None, None
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt        链表反转
        head2 = prev
        h1, h2 = head, head2  
        h = ListNode()        这里申请一个空节点,便于操作
        while h1 and h2:      while循环中交替链接
            h1_next, h2_next = h1.next, h2.next
            h.next = h1     
            h = h.next
            h.next = h2
            h = h.next
            h1, h2 = h1_next, h2_next
        #if h1:
        h.next = h1
个人总结:

此题的核心思想就是双指针法+链表反转+交替连接。思路上很基础没什么好说的,但是细节需要特别注意。Leetcode算法题关于细节上的各种处理,也是枯燥的刷题过程中令人拍手叫绝的有趣之处。






所属网站分类: 技术文章 > 博客

作者:丸子

链接:https://www.pythonheidong.com/blog/article/450921/ef2348547e9f3dce286f/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

25 0
收藏该文
已收藏

评论内容:(最多支持255个字符)