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.
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
- ##Input: head = [1,2]
- Output: [2,1]
Example 3:
- Input :head = []
- Output: []
# 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 skillsGiven 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).
{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 preKey formulaCatch 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.
Next, let’s give two examples:
Reversing the specified interval in the linked listInverting every k nodes in the linked listSpecified interval reversal in the linked listReversing 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,4Return 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.
- 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
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+1Threading the needle and thread part of the code:
nextNode = preHead.next preHead.next = pre if nextNode: nextNode.next = curComplete 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.nextFlip the nodes in the linked list every k groupsFlip the nodes in the given linked list every k groups and return the flip The last linked listIf the number of nodes in the linked list is not a multiple of k, keep the last remaining node as isYou 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},2Return 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!

Is it enough to learn Python for two hours a day? It depends on your goals and learning methods. 1) Develop a clear learning plan, 2) Select appropriate learning resources and methods, 3) Practice and review and consolidate hands-on practice and review and consolidate, and you can gradually master the basic knowledge and advanced functions of Python during this period.

Key applications of Python in web development include the use of Django and Flask frameworks, API development, data analysis and visualization, machine learning and AI, and performance optimization. 1. Django and Flask framework: Django is suitable for rapid development of complex applications, and Flask is suitable for small or highly customized projects. 2. API development: Use Flask or DjangoRESTFramework to build RESTfulAPI. 3. Data analysis and visualization: Use Python to process data and display it through the web interface. 4. Machine Learning and AI: Python is used to build intelligent web applications. 5. Performance optimization: optimized through asynchronous programming, caching and code

Python is better than C in development efficiency, but C is higher in execution performance. 1. Python's concise syntax and rich libraries improve development efficiency. 2.C's compilation-type characteristics and hardware control improve execution performance. When making a choice, you need to weigh the development speed and execution efficiency based on project needs.

Python's real-world applications include data analytics, web development, artificial intelligence and automation. 1) In data analysis, Python uses Pandas and Matplotlib to process and visualize data. 2) In web development, Django and Flask frameworks simplify the creation of web applications. 3) In the field of artificial intelligence, TensorFlow and PyTorch are used to build and train models. 4) In terms of automation, Python scripts can be used for tasks such as copying files.

Python is widely used in data science, web development and automation scripting fields. 1) In data science, Python simplifies data processing and analysis through libraries such as NumPy and Pandas. 2) In web development, the Django and Flask frameworks enable developers to quickly build applications. 3) In automated scripts, Python's simplicity and standard library make it ideal.

Python's flexibility is reflected in multi-paradigm support and dynamic type systems, while ease of use comes from a simple syntax and rich standard library. 1. Flexibility: Supports object-oriented, functional and procedural programming, and dynamic type systems improve development efficiency. 2. Ease of use: The grammar is close to natural language, the standard library covers a wide range of functions, and simplifies the development process.

Python is highly favored for its simplicity and power, suitable for all needs from beginners to advanced developers. Its versatility is reflected in: 1) Easy to learn and use, simple syntax; 2) Rich libraries and frameworks, such as NumPy, Pandas, etc.; 3) Cross-platform support, which can be run on a variety of operating systems; 4) Suitable for scripting and automation tasks to improve work efficiency.

Yes, learn Python in two hours a day. 1. Develop a reasonable study plan, 2. Select the right learning resources, 3. Consolidate the knowledge learned through practice. These steps can help you master Python in a short time.


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

MinGW - Minimalist GNU for Windows
This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

Dreamweaver CS6
Visual web development tools

WebStorm Mac version
Useful JavaScript development tools

ZendStudio 13.5.1 Mac
Powerful PHP integrated development environment

Notepad++7.3.1
Easy-to-use and free code editor