反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
思路:
- 遍历链表,抽离需要反转部分链表进行反转操作
- 头拼接与尾拼接
- 主要考察链表操作
代码:
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || head.next == null || m == n)
return head;
ListNode normal = head, last = null, pre, cur, gra = new ListNode(0);
gra.next = head;
pre = gra;
cur = head;
while (cur != null) {
if (m == 1) {
normal = cur;
// 链表反转,头拼接
last = reverseList(cur, pre, n);
// 尾拼接
normal.next = last;
break;
}
cur = cur.next;
pre = pre.next;
m--;
n--;
}
return gra.next;
}
// 反转链表工具方法,反转当前节点与之后n个节点的子链表,头拼接
public ListNode reverseList(ListNode head, ListNode first, int n) {
ListNode pre = null;
ListNode next = head;
while (n > 0) {
ListNode tmp = next.next;
next.next = pre;
pre = next;
next = tmp;
n--;
}
first.next = pre;
return next;
}
总结:
- 链表操作最好配合画图理解
- 当可能对头节点进行删改操作时,添加一个指向头节点的辅助节点
gra,用于最后的return - 节点赋值传递对象,原对象被修改时,被赋值的节点也会被修改
- 轻喷
