Skip to main content

Reverse Linked List II

Question​

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

How can the Reverse Linked List II algorithm be used to reverse the nodes of a linked list k at a time and return its modified list?

Example 1
Input: 1->2->3->4->5->NULL, m = 2, n = 4

Output: 1->4->3->2->5->NULL

Solution​

all//Reverse Linked List II.py


# 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:
        # Edge cases
        if not head:
            return None
        if m == n:
            return head

        # Create dummy node before head
        dummy = ListNode(-1)
        dummy.next = head
        curr = dummy

        # Find the node right before m
        for _ in range(m-1):
            curr = curr.next
        start = curr
        end = curr.next

        # Reverse the node from m to n
        prev = None
        for _ in range(n-m+1):
            next_node = end.next
            end.next = prev
            prev = end
            end = next_node

        start.next = prev
        curr.next = end

        return dummy.next