反转类题目,可以通过迭代与递归来解决,这篇文章主要讲述迭代方法,递归方法会在后面介绍到。
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# 处理特殊情况
if head == None or head.next == None:
return head
pre = None
cur = head
# t是中间指针,链表题中经常用到
while cur != None:
t = cur.next
cur.next = pre
pre = cur
cur = t
return pre
给你单链表的头指针 head 和两个整数 m 和 n ,其中 m <= n 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
示例:
输入:head = [1,2,3,4,5], m = 2, n = 4
输出:[1,4,3,2,5]
思路:
我们需要两个指针pre和cur。向前推进cur指针,prev指针跟随其后,直到cur指针到达从链表头起的第m个结点。
tail指针指向从链表头起的第m 个结点,此结点是反转后链表的尾部,故称为tail。con指针指向第m个结点的前一个结点,此结点是新链表的头部。
当cur指针抵达第m个结点后,迭代地反转链接,直到完成指向第n个结点的链接。此时,pre指针会指向第n个结点。
这时候,我们使用con指针来连接pre指针,类似地,我们利用tail指针来连接pre指针之后的结点(第n+1个结点)。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
pre = None
cur = head
count = 1
while count < left:
pre = cur
cur = cur.next
count += 1
# 循环结束时,cur指针指向left位置,pre指针指向前一个位置
# 记录
cont = pre
tail = cur
while count <= right:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
count += 1
# 循环结束时,pre指针指向right位置,cur指针指向right+1位置
if cont:
cont.next = pre
else:
head = pre
tail.next = cur
return head
出了错误的话,可以用如下方法来验证
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 生成链表的函数
def create_node_list(arr):
head = ListNode(arr[0])
cur = head
for i in range(1, len(arr)):
cur.next = ListNode(arr[i])
cur = cur.next
return head
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
pre = None
cur = head
count = 1
while count < left:
pre = cur
cur = cur.next
count += 1
# 循环结束时,cur指针指向left位置,pre指针指向前一个位置
# 记录
cont = pre
tail = cur
while count <= right:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
count += 1
# 循环结束时,pre指针指向right位置,cur指针指向right+1位置
if cont:
cont.next = pre
else:
head = pre
tail.next = cur
curr = head
data = []
while curr:
data.append(str(curr.val))
curr = curr.next
print('(Head) ' + ' -> '.join(data) + ' (Tail)')
return head
if __name__ == '__main__':
arr = [1, 2, 3, 4, 5]
left = 2
right = 4
head = create_node_list(arr)
s = Solution()
s.reverseBetween(head, left, right)
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
示例:
输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]
思路:
链表分区为已翻转部分+待翻转部分+未翻转部分。
每次翻转前,要确定翻转链表的范围,这个必须通过k次循环来确定,需记录翻转链表前驱pre和后继next,方便翻转完成后把已翻转部分和未翻转部分连接起来。同时,k个一组的链表的头和尾用start和end表示,start初始位于k个链表的第一个,而end初始位于其前驱。经过k次循环,end 到达末尾,记录待翻转链表的后继pre= end.next,并把end 断开。反转链表。然后将三部分链表连接起来,然后重置pre和end 指针,然后进入下一次循环。
结合下面图进行理解:
![]()
![]()
![]()
![]()
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
# 构造虚拟头结点
dummy = ListNode(0)
dummy.next = head
# 构造三个指针
pre = dummy
end = dummy # 经过K次循环,end到达末尾
start = head
while True:
# 经过K次循环,end到达一组的末尾
for _ in range(k):
end = end.next
if end == None:
break
# 链表到达末尾(差一个)
if end ==None:
break
third = end.next
end.next = None
# 反转大小为k的链表(返回反转后的头节点)
temp = self.reverse(start)
# 前面已完成反转部分的链表接上这个头节点
pre.next = temp
# 更新这几个指针
pre = start
end = start
start.next = third
start = start.next
return dummy.next
# 反转
def reverse(self,head):
dummy = ListNode(0)
pre = dummy
cur = head
while cur != None:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre
如果对您有帮助,麻烦点赞关注,这真的对我很重要!!!如果需要互关,请评论或者私信!
文章来源互联网,如有侵权,请联系管理员删除。邮箱:417803890@qq.com / QQ:417803890
Python Free
邮箱:417803890@qq.com
QQ:417803890
皖ICP备19001818号-4
© 2019 copyright www.pythonf.cn - All rights reserved
微信扫一扫关注公众号:
Python Free