Reverse Linked List II

Problem Id: 92 Difficulty: Medium Tag: Linked List


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 |
    |  |     |  |

Then we can first let point to None and then reverse the sub-linked list. Finally, we need to add the sub linked list back.

Edge cases:

  1. 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.

  2. 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.


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
# = 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
            count += 1
        start, before = curr, prev

        while count < n:
            curr, prev =, curr
            count += 1
        after, end =, curr = None

        start, end = self._reverse(start) = start = after


    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 =
   = prev
            prev = curr
            curr = tmp
        start = curr
        return prev, head