本文主要是介绍【LeetCode 92.】 反转链表 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1.题目
虽然本题很好拆解,但是实现起来还是有一些难度的。
2. 分析
- 尽可能抽象问题,然后简化代码
我在写本题的时候,遇到了下面这两个问题:
- 没有把[left,right] 这个区间的链表给断开,所以导致反转起来非常麻烦。所以在找到[left, right] 区间后,要将这个链表前后断开会比较方便操作。
- 正是因为问题1,导致我在反转链表的时候,使用了下面这版代码:
# Definition for singly-linked list.
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def reverseBetween(self, head: ListNode, left: int, right: int) :# 如果区间为1,不用反转if left == right:return headcnt = 1head_bak = headwhile(cnt < left):head_bak = head_bak.nextcnt+=1new_left = head_bakhead_bak = headcnt = 1while(cnt < right):head_bak = head_bak.nextcnt+=1new_right = head_bakprint(new_left.val, new_right.val)reversed_head = new_rightreversed_tail = new_leftsplit_head = headsplit_tail = new_right.nextwhile(split_head.next != new_left):split_head = split_head.next# 开始反转pre = Noneprint("hhh",new_right.next.val)cnt = 0 # 反转节点的个数# while(cnt < right-left+2): while(new_left != new_right.next):print(id(new_right.next))tmp = new_left.nextnew_left.next = prepre = new_leftnew_left = tmpcnt+=1# print(new_left.val , new_left == new_right.next, id(new_left), id(new_right.next))split_head.next = reversed_headreversed_tail.next = split_tailif reversed_tail == head:return reversed_headreturn headhead1 = ListNode(1)
head2 = ListNode(2)
head3 = ListNode(3)
head4 = ListNode(4)
head5 = ListNode(5)
head1.next = head2
head2.next = head3
head3.next = head4
head4.next = head5
head5.next = None
start = head1
while(start):print(id(start))start = start.next
s = Solution()
s.reverseBetween(head1, 2, 4)
这份代码有一个隐蔽的bug:
在 41 ~ 47 行之间。原因是 while 循环的过程中会把 new_right.next 的值给改掉(也就是44行的代码),因为new_right 指的是right那个地方的节点,这个节点new_left 在遍历的过程中也会访问。
这份代码最大的问题就是没有意识到这个new_right.next 值在while时候变化了。
3.代码
下面这份代码虽然可以过掉样例,但是代码很丑。
# Definition for singly-linked list.
# 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) :# 如果区间为1,不用反转if left == right:return headcnt = 1head_bak = headwhile(cnt < left):head_bak = head_bak.nextcnt+=1new_left = head_bakhead_bak = headcnt = 1while(cnt < right):head_bak = head_bak.nextcnt+=1new_right = head_bakprint(new_left.val, new_right.val)reversed_head = new_rightreversed_tail = new_leftsplit_head = Nonesplit_tail = new_right.nextcnt = 1hh_head = headwhile(cnt < left):split_head = hh_headhh_head = hh_head.next cnt += 1# 开始反转pre = None# print("hhh",new_right.next.val)cnt = 0 # 反转节点的个数while(cnt < right-left+1):# print(id(new_right.next))tmp = new_left.nextnew_left.next = prepre = new_leftnew_left = tmpcnt+=1# print(new_left.val , new_left == new_right.next, id(new_left), id(new_right.next))if split_head:split_head.next = reversed_headreversed_tail.next = split_tailif reversed_tail == head:return reversed_headreturn head
这篇关于【LeetCode 92.】 反转链表 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!