# LeetCode Reverse Linked List II: One Pass

## Overview

LeetCode Reverse Linked List II tests pointer manipulation. In one pass, the sub-list over m to n can be reversed in a single loop without post processing.

## LeetCode Reverse Linked List II Problem

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.

## Solution to Reverse in One Pass

No tricky algorithm here, it is just test your ability to use pointers well. Be careful when dealing with some border cases or NULL pointers. Just simulate the process of doing the reversing: use several pointers, scan through the list, when arrive the m-th node, start reversing until the n-th node, and concatenate this revered sub list with the other possible two remaining parts of the original list. Be extremely careful about special cases which might lead to NULL pointers. The following source code is quite elegant and simple but a bit hard to be understood intuitively, it is accepted by LeetCode OJ to pass this Reverse Linked List II problem:

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *reverseBetween(
int m, int n) {
m >= n) {
}

n -= m;
ListNode s(0);

ListNode *p1 = &s;
while (--m)
p1 = p1->next;
ListNode *p2 = p1->next;
ListNode *p3 = p2->next;

while (n--) {
p3 = p2->next;
p2->next = p3->next;
p3->next = p1->next;
p1->next = p3;
}
return s.next;
}
};
```

The following Java code might be easier to understand, and it is accepted by LeetCode OJ to pass this Reverse Linked List II problem as well:

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseBetween(
int m, int n) {
if (m >= n ||
}

ListNode s = new ListNode(0);

ListNode lt, rh, p1, p2, p3;
p1 = s;
p3 = p2.next;

for (int i = 1; i < m; ++i) {
p1 = p2;
p2 = p3;
p3 = p2.next;
}

lt = p1;

for (int i = m; i < n; ++i) {
p1 = p2;
p2 = p3;
p3 = p2.next;

p2.next = p1;
}

rh = p3;
lt.next.next = rh;
lt.next = p2;

return s.next;
}
}
```

Note:

1. And regarding with the time/space complexity, the above implementation takes O(n) time and O(1) space with a single pass over the linked list.
2. This problem is a generalized version of this problem: LeetCode Reverse Linked List: Recursive VS Iterative Solution , you can take a look at that as well

## Summary

LeetCode Reverse Linked List II tests pointer manipulation. In one pass, the sub-list over m to n can be reversed in a single loop without post processing.

Written on May 20, 2013