Reverse Linked List II
Intuition
In the given example, 1->2->3->4->5->NULL, we need to reverse 2->3->4. To make sure we don't miss the previous and next node after the reversed sub-linked list, we need to use 2 pointer to point to prev and end node. Like below.
start after
before | end |
| | | |
1->2->3->4->5->NULL
Then we can first let end.next point to None and then reverse the sub-linked list. Finally, we need to add the sub linked list back.
Edge cases:
What if prev is None and start from th first node?
We need prev to point to the new reversed linked list. If prev is None, we need to directly return the head of sub linked list. But if we add a empty head before the whole list, we will not need to handle this case.
What if next is None?
We will point the end of reversed linked list to next. So it doesn't matter whether it point to None or not.
Solution
# 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, m: int, n: int) -> ListNode:
if m >= n:
return head
head = ListNode(None, next=head)
prev = None
curr = head
count = 0
while count < m:
curr, prev = curr.next, curr
count += 1
start, before = curr, prev
while count < n:
curr, prev = curr.next, curr
count += 1
after, end = curr.next, curr
end.next = None
start, end = self._reverse(start)
before.next = start
end.next = after
return head.next
def _reverse(self, head):
"""Reverse the linked list and return the start and end node of the
linked list."""
prev = None
curr = head
while curr:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
start = curr
return prev, head