链表内指定区间反转

描述

答案：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode node = new ListNode(-1);
        node.next = head;
        ListNode p = node;
        for (int i = 0; i < m - 1; i++) {
            p = p.next;
        }
        ListNode x = p.next;
        ListNode x_next;
        for (int i = m; i < n; i++) {
            x_next = x.next;
            x.next = x_next.next;
            x_next.next = p.next;
            p.next = x_next;
        }
        return node.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

核心代码分析：

核心代码：

ListNode x = p.next;
ListNode x_next;
for (int i = m; i < n; i++) {
    x_next = x.next;
    x.next = x_next.next;
    x_next.next = p.next;
    p.next = x_next;
}
1
2
3
4
5
6
7
8

eg:p：4 3 5 2
x：3 5 2
x_next：x.next (一直指向x的next)
一次循坏结束后： p：4 5 3 2
第一步：将3移到5的后面，即x.next=x_next.next得x:3 2
第二步：将5移到3的前面，即x_next.next=p.next得x_next:5 3 2
第三步：将x_next移到p后面，即p.next=x_next得p：4 5 3 2