LeetCode.092.Reverse Linked List II 反转链表的第m到n个结点

题目描述

92 Reverse Linked List II https://leetcode-cn.com/problems/reverse-linked-list-ii/

Reverse a linked list from position m to n. Do it in one-pass. Note: 1 ≤ m ≤ n ≤ length of list. Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

相似题目

LeetCode.206.Reverse Linked List 反转链表 LeetCode.092.Reverse Linked List II 反转链表的第m到n个结点 LeetCode.025.Reverse Nodes in k-Group K 个一组翻转链表

解题过程

反转链表的第m到n个结点 双指针，cur指向m结点，pre指向m的前一个结点，从m+1到n依次插入到pre之后即可。 时间复杂度 O(n)，空间复杂度 O(1)

public ListNode reverseBetween(ListNode head, int m, int n) {
    if (null == head || null == head.next || m == n) {
        return head;
    }
    // 头结点
    ListNode newHead = new ListNode(0);
    newHead.next = head;
    ListNode pre = newHead, cur = head;
    for (int i = 1; i < n; i++) {
        if (i < m) {
            // cur移到需要反转的起始结点m，pre是前一个结点
            pre = cur;
            cur = cur.next;
        } else {
            // 从m+1到n，依次插入到pre后即可
            ListNode temp = cur.next;
            cur.next = cur.next.next;
            temp.next = pre.next;
            pre.next = temp;
        }
    }
    return newHead.next;
}

GitHub代码

algorithms/leetcode/leetcode/_092_ReverseLinkedList2.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_092_ReverseLinkedList2.java