Reverse Linked List II

Problem Id: 92 Difficulty: Medium Tag: Linked List


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:

  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.

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