給你單鍊錶的頭節點head ，請你反轉鍊錶，並返回反轉後的鍊錶。
輸入：頭 = [1,2,3,4,5]
輸出： [5,4,3,2,1]
#輸入：頭 = [1,2]
輸出：[2,1]
#範例3：
輸入：head = []
輸出：[]
# 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 # 返回一个新的链表給定一個單鍊錶的頭結點pHead(該頭節點是有值的，例如在下圖，它的val是1)，長度為n，反轉該鍊錶後，返回新鍊錶的表頭。
要求：空間複雜度 O(1)O(1) ，時間複雜度 O(n)O(n) 。
輸入：
{1,2,3}
傳回值：
#{3,2,1}
先來看最基本的反轉鍊錶碼：
# -*- 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抓住幾個關鍵點：
cur：原鍊錶的頭節點，在反轉結束時，cur指向pre的下一個節點
接下來，舉兩個例子：
鍊錶內指定區間反轉鍊錶中的節點每k個一組翻轉鍊錶內指定區間反轉將一個節點數為size 鍊錶m 位置到 n 位置之間的區間反轉，要求時間複雜度O(n)，空間複雜度 O(1 )。#：時間複雜度 O(n) ，空間複雜度 O(n)
進階：時間複雜度 O(n)，空間複雜度 O (1)輸入：{1,2,3,4,5},2,4傳回值：
{1,4,3,2,5}
套用公式
這題目和baseline的差別是，是將整個鍊錶的反轉改成鍊錶m 位置到 n 位置之間的區間反轉，來套一下公式：
先看下套公式部分的程式碼：
# 找到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穿針引線部分程式碼：
nextNode = preHead.next
preHead.next = pre
if nextNode:
nextNode.next = cur完整程式碼：
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鍊錶中的節點每k個一組翻轉
如果鍊錶中的節點數不是k 的倍數，將最後剩下的節點保持原樣
你不能改變節點中的值，只能改變節點本身。
要求空間複雜度O(1)，時間複雜度 O(n)#輸入：
##{1,2, 3,4,5},2
傳回值：
{2,1,4,3,5}
套用公式
這題目和baseline的差別是，是將整個鍊錶的反轉改成每k個一組反轉，如果節點數不是k的倍數，剩下的節點保持原樣。
先分段來看，假設面對位置1-位置k的鍊錶：#原始鍊錶的頭節點：cur：從head出發，再走k -1步，到達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，后面会提到显式指定。
以上是python鍊錶的反轉方式是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！
