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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode preNode = dummy;
for (int i = 1; i <= m - 1; i++) {
preNode = preNode.next;
}
ListNode curNode = preNode.next;
ListNode nextNode = curNode.next;
for (int i = m; i < n; i++) {
curNode.next = nextNode.next;
nextNode.next = preNode.next;
preNode.next = nextNode;
nextNode = curNode.next;
}
return dummy.next;
}
}
3. Time & Space Complexity
时间复杂度O(m - n + 1), 空间复杂度O(1)
Last updated
Was this helpful?