# Leetcode: Reverse Linked List II

Reverse a linked list from position m to n.

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

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 <= m <= n <= length of list.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/reverse-linked-list-ii
## Basic Ideas: Insert to a given pointer for (n-m) times.
##       1. Change in the head, thus we need a dummy head node
##       2. Need to track get previous node of sub list
##       3. Need to track the head of original sub list
##       4. How many times each loop shall compute
## Complexity: Time O(n), Space O(1)
## Sample Data
##      1->2->3->4->5->6->NULL, m = 2 and n = 5
##         .  .  .  .
##      p     q  r
##
##      1->2->3->4->5->NULL, m = 1 and n = 3
##      .  .  .
##      p
##
##      3->5
##     dummy -> 3 -> 5
##       p
##              q     r
##     dummy -> 1 -> 2 -> 3
##       p      q    r

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:type m: int
:type n: int
:rtype: ListNode
"""
# Nothing changed
if m == n:
dummyNode = ListNode(0)
p = dummyNode
# p: points to the previous node of the sublist head
for i in xrange(m-1):
p = p.next
# r points to current node
# q points to the original first node of the sublist
# No need to reverse the first node
q = p.next
r = q.next
for i in xrange(n-m):
q.next = r.next
r.next = p.next
p.next = r
r = q.next
return dummyNode.next
```

Share It, If You Like It.