0092. Reversed Linked List ii

Problem

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.

Examples

Example 1:

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

Example 2:

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

Constraints:

The number of nodes in the list is n.
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

Follow-up

Analysis

# some definitions
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val 
        self.next = next 

def list_to_linkedlist(list):
    head = ListNode()
    node = head
    for v in list:
        v_node = ListNode(v)
        node.next = v_node
        node = node.next

    return head.next

def print_linkedlist(linked_list):
    res = []
    while linked_list:
        res.append(linked_list.val)
        linked_list = linked_list.next
    print(res)
    
list = [1,2,3,4,5]
head = list_to_linkedlist(list)
print_linkedlist(head)

[1, 2, 3, 4, 5]

# solution 1: two pointers O(N) in time, and O(1) in space
# one for current node, and the other for previous node
# 1-2-3-4-5-6 -> 1-2-3-4-5 -> 2-1 3-4-5 -> 3-2-1 4-5 -> 4-3-2-1 5 -> 5-4-3-2-1
# find and save the left node 
# move pointer right until the right node is found
# reverse the nodes from left to right
def solution(head, left, right):
    
    # empty list

    # move two pointers till the left node
    prev, cur = None, head
    while left > 1:
        prev = cur
        cur = cur.next
        left -= 1
        right -= 1
    
    # find the left node and save two pointers for final use
    hea = prev
    tail = cur 

    # reverse
    while right > 0:
        next = cur.next # save the next node as cur.next will be swaped
        cur.next = prev

        # move forward
        prev = cur 
        cur = next
        right -= 1

    # connect the previous "left" node, the reversed nodes from "left" to "right", and the "right" nodes
    if hea:
        hea.next = prev 
    else:
        head = prev
    if tail:
        tail.next = cur 

    return head

#test
list = list_to_linkedlist([1,2,3,4,5])
left = 2
right = 4
print_linkedlist(solution(list, left, right))

list = list_to_linkedlist([5])
left = 1
right = 1
print_linkedlist(solution(list, left, right))


list = list_to_linkedlist([2,5])
left = 1
right = 2
print_linkedlist(solution(list, left, right))

[1, 4, 3, 2, 5]
[5]
[5, 2]