92 Reverse Linked List II

1. Question

Reverse a linked list from positionmton. Do it in-place and in one-pass.
For example: Given1->2->3->4->5->NULL,m= 2 andn= 4,
return1->4->3->2->5->NULL.
Note: Givenm,nsatisfy the following condition: 1 ≤m≤n≤ length of list.

2. Implementation

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) { val = x; }
7
* }
8
*/
9
class Solution {
10
public ListNode reverseBetween(ListNode head, int m, int n) {
11
ListNode dummy = new ListNode(0);
12
dummy.next = head;
13
14
ListNode preNode = dummy;
15
16
for (int i = 1; i <= m - 1; i++) {
17
preNode = preNode.next;
18
}
19
20
ListNode curNode = preNode.next;
21
ListNode nextNode = curNode.next;
22
23
for (int i = m; i < n; i++) {
24
curNode.next = nextNode.next;
25
nextNode.next = preNode.next;
26
preNode.next = nextNode;
27
nextNode = curNode.next;
28
}
29
return dummy.next;
30
}
31
}
Copied!

3. Time & Space Complexity

时间复杂度O(m - n + 1), 空间复杂度O(1)