search
HomeBackend DevelopmentPython TutorialWhat is the inversion method of python linked list

    Reversal of python linked list

    Reverse linked list

    I give you the head node of the singly linked list, please reverse the linked list. And return the reversed linked list.

    What is the inversion method of python linked list

    • Input: head = [1,2,3,4,5]

    • Output: [5,4,3,2,1]

    What is the inversion method of python linked list

    • ##Input: head = [1,2]

    • Output: [2,1]

    Example 3:

    • Input :head = []

    • Output: []

    Solution

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        """
        解题思路:
        1.新建一个头指针
        2.遍历head链表,依次在新的头节点位置插入,达到反转的效果
        """
        def reverseList(self, head: ListNode) -> ListNode:
            # 循环
            new_head = None
    
            while head:
                per = head.next # pre 为后置节点,及当前节点的下一个节点
    
                head.next = new_head # 插入头节点元素
    
                new_head = head # 把串起来的链表赋值给头指针
    
                head = per  # 向后移一个单位
            
            return  new_head  # 返回一个新的链表

    Python reversal linked list related skills

    Given the head node pHead of a singly linked list (the head node has a value, for example, in the figure below, its val is 1), the length is n, after reversing the linked list, return the head of the new linked list.

    Requirements: Space complexity O(1)O(1), time complexity O(n)O(n).

    What is the inversion method of python linked list

    Input:

    {1,2,3}

    Return value:

    {3,2,1}

    Let’s first look at the most basic reverse linked list code:

    # -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        # 返回ListNode
        def ReverseList(self, pHead):
            # write code here
            cur = pHead
            pre = None
            while cur:
                nextNode = cur.next
                cur.next = pre
                pre = cur
                cur = nextNode
            return pre

    Key formula

    Catch a few Key points:

    • cur: The head node of the original linked list. At the end of the inversion, cur points to the next node of pre

    • pre: The tail node of the original linked list is the head node of the reversed linked list. The final return is pre.

    • while cur: Indicates the condition for reversing the loop, here is to determine whether cur is empty. You can also change it to other loop conditions according to the conditions of the question

    • Reverse the tail node of the linked list. The tail node here is None, and explicit specification will be mentioned later.

    For the problem of reversing the linked list, grasp the main roles of the head node of the original linked list, the tail node of the original linked list, the reverse loop condition, and the tail node of the reversed linked list. Basically no problem.

    Next, let’s give two examples:

    Reversing the specified interval in the linked list

    Inverting every k nodes in the linked list

    Specified interval reversal in the linked list

    Reversing the interval between the m position and the n position of a linked list with a node number of size requires time complexity O(n) and space complexity O(1 ).

    Requirements: time complexity O(n), space complexity O(n)

    Advanced: time complexity O(n), space complexity O (1)

    Input:

    {1,2,3,4,5},2,4

    Return value:

    {1,4,3,2,5}

    Apply the formula

    The difference between this question and baseline is that Change the reversal of the entire linked list to the reversal of the interval between the m position and the n position of the linked list. Let's apply the formula:

    • The head node of the original linked list: cur: starting from head , then take m-1 steps to reach cur

    • The tail node of the original linked list: pre: The node in front of cur

    • Reverse loop condition : for i in range(n,m)

    • Reverse the tail node of the linked list: you need to save it starting from head, then go m-1 steps, when you reach cur, at this time pre position prePos. prePos.next is the tail node of the reverse linked list.

    is compared with the previous one. Additional attention is required:

    • needs to be saved and started from head. , take m-1 steps again, and when you reach cur, the position of pre at this time is prePos. After the reversal cycle ends, start threading again

    • Since the entire linked list is not reversed, it is best to create a new virtual head node dummyNode, and dummyNode.next points to the entire linked list

    What is the inversion method of python linked list

    Code implementation

    First look at the code of the formula part:

    # 找到pre和cur
    i = 1
    while i<m:
        pre = cur
        cur = cur.next
        i = i+1
     
    # 在指定区间内反转
    preHead = pre
    while i<=n:
        nextNode = cur.next
        cur.next = pre
        pre = cur
        cur = nextNode
        i = i+1

    Threading the needle and thread part of the code:

    nextNode = preHead.next
    preHead.next = pre
    if nextNode:
        nextNode.next = cur

    Complete code:

    class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
     
    class Solution:
        def reverseBetween(self , head , m , n ):
            # write code here
            dummpyNode = ListNode(-1)
            dummpyNode.next = head
            pre = dummpyNode
            cur = head
     
            i = 1
            while i<m:
                pre = cur
                cur = cur.next
                i = i+1
     
            preHead = pre
            while i<=n:
                nextNode = cur.next
                cur.next = pre
                pre = cur
                cur = nextNode
                i = i+1
            
            nextNode = preHead.next
            preHead.next = pre
            if nextNode:
                nextNode.next = cur
     
            return dummpyNode.next

    Flip the nodes in the linked list every k groups

    Flip the nodes in the given linked list every k groups and return the flip The last linked list

    If the number of nodes in the linked list is not a multiple of k, keep the last remaining node as is

    You cannot change the value in the node, only the node itself.

    Requires space complexity O(1), time complexity O(n)

    Input:

    {1,2, 3,4,5},2

    Return value:

    {2,1,4,3,5}

    Apply formula

    The difference between this question and the baseline is that the inversion of the entire linked list is changed to a group of k inversions. If the number of nodes is not a multiple of k, the remaining The nodes remain as they are.

    Let’s look at it in sections first. Suppose we face a linked list from position 1 to position k:

    • The head node of the original linked list: cur: start from head and go k -1 step to reach cur

    • 原链表的尾节点:pre:cur前面的节点

    • 反转循环条件:for i in range(1,k)

    • 反转链表的尾节点:先定义tail=head,等反转完后tail.next就是反转链表的尾节点

    先看下套公式部分的代码:

    pre = None
    cur = head
    tail = head
     
     
    i = 1
    while i<=k:
        nextNode = cur.next
        cur.next = pre
        pre = cur
        cur = nextNode
        i = i+1

    这样,我们就得到了1 位置1-位置k的反转链表。

    此时:

    • pre:指向反转链表的头节点

    • cur:位置k+1的节点,下一段链表的头节点

    • tail:反转链表的尾节点

    那么,得到位置k+1-位置2k的反转链表,就可以用递归的思路,用tail.next=reverse(cur,k)

    需要注意:如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样

    i = 1
    tmp = cur
    while i<=k:
        if tmp:
            tmp = tmp.next
        else:
            return head
        i = i+1

    代码实现

    完整代码:

    class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
     
    class Solution:
        def reverseKGroup(self , head , k ):
           
            # write code here
            return self.reverse(head, k )
        
        def reverse(self , head , k ):
            pre = None
            cur = head
            tail = head
     
            i = 1
            tmp = cur
            while i<=k:
                if tmp:
                    tmp = tmp.next
                else:
                    return head
                i = i+1
            
            i = 1
            while i<=k:
                nextNode = cur.next
                cur.next = pre
                pre = cur
                cur = nextNode
                i = i+1
     
            tail.next = self.reverse(cur, k)
            return pre

    好了,抓住几个关键点:

    • cur:原链表的头节点,在反转结束时,cur指向pre的下一个节点

    • pre:原链表的尾节点,也就是反转后链表的头节点。最终返回的是pre。

    • while cur:表示反转循环的条件,这里是判断cur是否为空。也可以根据题目的条件改成其他循环条件

    • 反转链表的尾节点,这里的尾节点是None,后面会提到显式指定。

    The above is the detailed content of What is the inversion method of python linked list. For more information, please follow other related articles on the PHP Chinese website!

    Statement
    This article is reproduced at:亿速云. If there is any infringement, please contact admin@php.cn delete
    详细讲解Python之Seaborn(数据可视化)详细讲解Python之Seaborn(数据可视化)Apr 21, 2022 pm 06:08 PM

    本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于Seaborn的相关问题,包括了数据可视化处理的散点图、折线图、条形图等等内容,下面一起来看一下,希望对大家有帮助。

    详细了解Python进程池与进程锁详细了解Python进程池与进程锁May 10, 2022 pm 06:11 PM

    本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于进程池与进程锁的相关问题,包括进程池的创建模块,进程池函数等等内容,下面一起来看一下,希望对大家有帮助。

    Python自动化实践之筛选简历Python自动化实践之筛选简历Jun 07, 2022 pm 06:59 PM

    本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于简历筛选的相关问题,包括了定义 ReadDoc 类用以读取 word 文件以及定义 search_word 函数用以筛选的相关内容,下面一起来看一下,希望对大家有帮助。

    归纳总结Python标准库归纳总结Python标准库May 03, 2022 am 09:00 AM

    本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于标准库总结的相关问题,下面一起来看一下,希望对大家有帮助。

    分享10款高效的VSCode插件,总有一款能够惊艳到你!!分享10款高效的VSCode插件,总有一款能够惊艳到你!!Mar 09, 2021 am 10:15 AM

    VS Code的确是一款非常热门、有强大用户基础的一款开发工具。本文给大家介绍一下10款高效、好用的插件,能够让原本单薄的VS Code如虎添翼,开发效率顿时提升到一个新的阶段。

    python中文是什么意思python中文是什么意思Jun 24, 2019 pm 02:22 PM

    pythn的中文意思是巨蟒、蟒蛇。1989年圣诞节期间,Guido van Rossum在家闲的没事干,为了跟朋友庆祝圣诞节,决定发明一种全新的脚本语言。他很喜欢一个肥皂剧叫Monty Python,所以便把这门语言叫做python。

    Python数据类型详解之字符串、数字Python数据类型详解之字符串、数字Apr 27, 2022 pm 07:27 PM

    本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于数据类型之字符串、数字的相关问题,下面一起来看一下,希望对大家有帮助。

    详细介绍python的numpy模块详细介绍python的numpy模块May 19, 2022 am 11:43 AM

    本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于numpy模块的相关问题,Numpy是Numerical Python extensions的缩写,字面意思是Python数值计算扩展,下面一起来看一下,希望对大家有帮助。

    See all articles

    Hot AI Tools

    Undresser.AI Undress

    Undresser.AI Undress

    AI-powered app for creating realistic nude photos

    AI Clothes Remover

    AI Clothes Remover

    Online AI tool for removing clothes from photos.

    Undress AI Tool

    Undress AI Tool

    Undress images for free

    Clothoff.io

    Clothoff.io

    AI clothes remover

    AI Hentai Generator

    AI Hentai Generator

    Generate AI Hentai for free.

    Hot Article

    R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
    2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
    Repo: How To Revive Teammates
    4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
    Hello Kitty Island Adventure: How To Get Giant Seeds
    4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

    Hot Tools

    Dreamweaver CS6

    Dreamweaver CS6

    Visual web development tools

    SecLists

    SecLists

    SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.

    MantisBT

    MantisBT

    Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

    mPDF

    mPDF

    mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

    ZendStudio 13.5.1 Mac

    ZendStudio 13.5.1 Mac

    Powerful PHP integrated development environment