[LeetCode] Challenge log 92

Posted on | Edited on |
92. Reverse Linked List II

Algorithm:

  1. find (m-1)th node
  2. reverse (n-m+1) nodes

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

1
2
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if not head or not head.next: return head
        
        # build virture head to aviod bound problem
        virtureHead = ListNode(0)
        virtureHead.next = head
        head = virtureHead
        
        # find (m-1)th 
        pre = head
        for i in range(m-1):
            pre = pre.next
          
        # reverse n-m+1 following elements 
        tail = None
        cur = pre.next
        count = 0
        while count < n - m + 1:
            nxt = cur.next
            cur.next = tail
            tail = cur
            cur = nxt
            count += 1

        # pm + tail + cur
        pre.next.next = cur
        pre.next = tail
        
        return head.next
0%