May 17, 2021

Leetcode 92 Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

image




Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]



Input: head = [5], left = 1, right = 1
Output: [5]
  • Soruda bize bir linked list ve içerisinde iki nokta veriliyor.Bu iki nokta arasındaki nodeları ters çevirmemiz isteniyor.
  • Kod kısmında açıklamaları yazdım. Burada yardımcı olması açısından bir dummy node kullanıyoruz.Bu bir çok edge case önlüyor.
  • Daha sonra verilern iki nokta arasındaki nodeları ters çeviriyoruz.
  • Son olarakta pointerları düzenliyoruz.
class Solution:

    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(0,head)
        
        #1) reach node at position "left"
        leftPrev, cur = dummy, head
        for i in range(left - 1):
            leftPrev, cur = cur, cur.next
        
        # Now cur="left", leftPrev="node before left"
        # 2) reverse from left to right
        prev = None
        for i in range(right - left + 1):
            tmpNext = cur.next
            cur.next = prev
            prev, cur = cur, tmpNext
        
        #3) Update pointers
        leftPrev.next.next = cur #cur is node after "right"
        leftPrev.next = prev     #prev is right
        return dummy.next