1 题目
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.
接口
ListNode reverseBetween(ListNode head, int m, int n)
2 思路
采用就地反转链表。找到m节点，之后每读到一个结点，把它插入到m结点前面位置，然后m结点接到读到结点的下一个。
- 第一步是找到m结点所在位置.
- 第二步是从节点m到n依次反转指针.
复杂度
Time: O(n) 总共只需要一次扫描，所以时间是O(n)
Space: O(1) 只需要几个辅助指针，空间是O(1)。
3 代码
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
for (int i = 0; i < m - 1; i++) {
prev = prev.next;
}
// 就地反转法
ListNode dummy2 = prev;
prev = dummy2.next;
ListNode pCur = prev.next;
for (int i = m - 1; i < n - 1; i++) {
prev.next = pCur.next;
pCur.next = dummy2.next;
dummy2.next = pCur;
pCur = prev.next;
}
return dummy.next;
}
4 总结
常见的链表反转操作，反转链表的一部分。
5 扩展
熟练掌握链表反转的2种方法，适当运用。