92. Reverse Linked List II

Problem Statement

link: LeetCode.cn LeetCode 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.

Example:

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]

Solution Approach

To reverse a portion of a linked list between positions left and right, iterate through the list until reaching the node before position left. Then, reverse the nodes between left and right using iterative swapping.

Algorithm

1. Traverse the list until reaching the node before position left.
2. Reverse the nodes between positions left and right using iterative swapping.
3. Ensure proper handling of pointers to maintain the integrity of the linked list structure.

Implement

    # Definition for singly-linked list. # class ListNode(object): #     def __init__(self, val=0, next=None): #         self.val = val #         self.next = next class Solution(object):
    def reverseBetween(self, head, left, right):
        """
        :type head: ListNode
        :type left: int
        :type right: int
        :rtype: ListNode
        """
        if head is None:
            return head

        dummy = ListNode(0)
        dummy.next = head
        prev =  dummy

        for _ in range(left - 1): # do not change
            prev = prev.next

        cur = prev.next
        for i in range(right - left):
            print(head)
            temp = cur.next
            cur.next = temp.next
            temp.next = prev.next # this is prev.next not cur, curr is moving, prev is not 
            prev.next = temp
        return dummy.next # here is dummy.next not head

    
    

Twitter  facebook  Email