Python Algorithm Q19

Q19 Reverse Linked List II

---

Q

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. Note that index starts from 1.

Sample Input

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]

Constraints

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

1. My own Solution == Given Solution

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

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        
        #definition of the rev function
        def rev(head: ListNode, length: int):
            rev = None
            for i in range(length-1):
                rev, rev.next, head = head, rev, head.next
            last_add = head.next
            rev, rev.next = head, rev
            return rev, last_add
        
        #filtering single node-list
        if not head.next:
            return head
        
        #saving head node
        #start is for saving "prevhead", not head
        prevhead = start = ListNode(0, head)

        #push until reaches the reverse point
        for i in range(left-1):
            prevhead = prevhead.next

        prevhead.next, lastadd = rev(prevhead.next, right-left+1)

        while prevhead.next:
            prevhead = prevhead.next

        #combine with last point
        prevhead.next = lastadd

        return start.next

inp1= [1,2,3,4,5,6,7,8,9]
def makeLinkedList(inp: List) -> ListNode:
    node = ListNode()
    head = node
    for val in inp:
        new_node = ListNode(val)
        new_node.next = node.next
        node.next = new_node
        node = node.next
    return head

link1 = makeLinkedList(inp1).next

#for test
a = Solution()
head_node = a.reverseBetween(link1, 1, 5)
while head_node:
    print(head_node.val)
    head_node = head_node.next

Really confusing and intricated, but finally, AGAIN, I solved it by myself!! Maybe explaining my answer will take so much time… Anyway, let’s start step by step.

1. rev function : this function takes head node and length as argument. As you can see, this is almost same as the function that we used at Q15. What is different is I used for loop instead of while loop. Repeat reversing (length-1) times. Then you can reach the last node to reverse. We need to save the address that last node contains. Assign it to the last_add. Then repeat the loop and return the value, rev(head node of the revesed linked-list) and last_add.

2. Filtering the case when the input is the single node. Because of the constraints, empty list does not exist. So we only need to filter the single node.

3. Save the head node. We need to return the head node at the end. Variable prevhead is moved to the end, so use the variable start as the return. Note that both are in front of the node head.

4. Push the node prevhead until this reaches left-index node(The node that reversing starts).

5. Make prevhead point the head node of the reversed list. Also get last_add(Saved to lastadd).

6. Push prevhead until the loop meets None. Properly speaking, push it to the point that reversing ends.

7. Combine prevhead with the remained(list).

8. Return start.next. You can question why you didn’t return head. It is because, the list that head points does not changed by the rev function at all. So returning head is meaningless. Therefore we should return prevhead, but prevhead points the lastadd. So I used extra varable start instead.

2. Given Solution #1

def reverseBetween(self, head: ListNode, m:int, n: int)-> ListNode:
    #exeception
    if not head or m==n:
        return head

    root start = ListNode(None)
    root.next = head

    #Designate start, end
    for _ in range(m-1):
        start = start.next
    end = start.next

    #repeating reversing the node in turn
    for _ in range(n-m):
        tmp, start.next, end.next = start.next, end.next, end.next.next
        start.next.next = tmp

    return root.next

Very simple and impressive code.

1. Starts with filtering the case when left==right or empty list.

2. Make the node before head, named root and start.

3. Assign start and end. start is literally the point that reversing starts. end is right behind start.

4. ** Repeat swapping nodes n-m times. Concept is do reverse by repeating swapping. For example, let list1 2->3->4->X. Pull second node, then 3->2->4->X. Lastly pull third node, then 4->3->2->X.

Those are the main points. It’s not difficult to simulate the process of the codes above. Try it if you forgot the concept of this answer.

Overall Review

Just solving the problem is not that hard, but this question makes me think so much. I need to consider the necessity of the node root. Also devising the function rev is quiet confusing. Even though, I solved it without any help. I’m experiencing my vivid growth in utilizing linked-list. Keep going!