题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度

样例

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

算法分析

反转从位置 m 到 n 的链表，先找到第m - 1的位置p，以及第n的位置q，a指向第m的位置，b指向第n + 1的位置

• 1、将[m,n]位置的元素进行翻转，借助c，d，e三个指针，具体操作看代码
• 2、将a.next指针指向b指针
• 3、将p.next指针指向q指针

时间复杂度$O(n)$

Java 代码

/**
 * 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 p = dummy;
        ListNode q = dummy;
        for(int i = 0;i < m - 1;i ++) p = p.next;
        for(int i = 0;i < n ;i ++) q = q.next;

        ListNode a = p.next;
        ListNode b = q.next;
        for(ListNode c = p.next,d = c.next;d != b;)
        {
            ListNode e = d.next;
            d.next = c;
            c = d;
            d = e;
        }

        a.next = b;
        p.next = q;

        return dummy.next;
    }
}