LeetCode——翻转链表II

NO.92 翻转链表II 中等

思路一：迭代实现 先找到需要进行反转的区间，然后翻转区间中的这个链表，最后将翻转完成的链表连接回原链表。

public ListNode reverseBetween(ListNode head, int m, int n) {
    if (head == null || head.next == null) return head;
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    //待翻转链表的头节点的前驱
    ListNode pre = dummy;
    for (int i = 0; i < m - 1; i++) pre = pre.next;
    //待翻转链表
    ListNode start = pre.next, end = pre.next;
    for (int i = 0; i < n - m; i++) end = end.next;
    //待翻转链表的后继
    ListNode next = end.next;
    //断开待翻转链表
    end.next = null;
    //翻转完成后拼接回原链表
    pre.next = reverse(start);
    start.next = next;
    return dummy.next;
}

//翻转链表
private ListNode reverse(ListNode head) {
    if (head.next == null) return head;
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

时间复杂度：O(n)

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github