题目:
题解:
分析:
第一步:找到待反转节点的前一个节点。
第二步:反转m到n这部分。
第三步:将反转的起点的next指向反转的后面一部分。
第四步:将第一步找到的节点指向反转以后的头节点。
结合 206. 反转链表,如下图所示:(注:图中的"next"即为代码中的"tmp"变量)
代码:
/** * code92 */
public class code92 {
public static ListNode reverseBetween(ListNode head, int m, int n) {
ListNode res = new ListNode(0);
res.next = head;
ListNode node = res;
// 找到需要反转的那一段的上一个节点。
for (int i = 1; i < m; i++) {
node = node.next;
}
// node.next就是需要反转的这段的起点。
//申请节点,pre和 cur,pre指向null
ListNode cur = node.next;
ListNode tmp = null;
ListNode pre = null;
// 反转m到n这一段
for (int i = m; i <= n; i++) {
//记录当前节点的下一个节点
tmp = cur.next;
//然后将当前节点指向pre
cur.next = pre;
//pre和cur节点都前进一位
pre = cur;
cur = tmp;
}
// 将反转的起点的next指向tmp。
node.next.next = tmp;
// 需要反转的那一段的上一个节点的next节点指向反转后链表的头结点
node.next = pre;
return res.next;
}
public static void print(ListNode node) {
if (node == null) {
return;
}
ListNode current = node;
while (current != null) {
System.out.print(current.val + " -> ");
current = current.next;
}
System.out.println("NULL");
}
public static void main(String[] args) {
ListNode listNode1 = new ListNode(1);
ListNode listNode2 = new ListNode(2);
ListNode listNode3 = new ListNode(3);
ListNode listNode4 = new ListNode(4);
ListNode listNode5 = new ListNode(5);
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
int m = 2;
int n = 4;
ListNode head = reverseBetween(listNode1, m, n);
print(head);
}
}