反转链表II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置right 的链表节点，返回 反转后的链表 。

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

方法：分解后拼接

算法思路：

  1. 设置哑节点dummyNode，记录开始位置。
  2. 设置pre节点，位移到需反转链表前一位，设置节点leftNode = pre.next后，执行pre.next = null断开链接。
  3. 设置rightNode = pre，位移至需反转链表末位，记录cur = rightNode.next，执行rightNode.next = null断开链接。
  4. 编写反转链表代码，反转leftNode。
  5. pre.next = rightNode与leftNode.next = cur链接三段链表。

代码实现：

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;

        for(int i = 0; i < left - 1; i++){
            pre = pre.next;
        }
				//找到leftNode节点
        ListNode leftNode = pre.next;
				//找到rightNode节点
        ListNode rightNode = pre;
        for(int i = 0; i < right - left + 1; i++){
            rightNode = rightNode.next;
        }
				//断开链表
        pre.next = null;
        ListNode cur = rightNode.next;
        rightNode.next = null;

        reverseListNode(leftNode);
				//链接三段链表
        pre.next = rightNode;
        leftNode.next = cur;

        return dummyNode.next;
    }

    public void reverseListNode(ListNode head){
        ListNode pre = new ListNode(-1);
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }
}

复杂度分析：

  • 时间复杂度：O(n)O(n)，其中nn是链表总节点数。最坏情况下，需要遍历整个链表。
  • 空间复杂度：O(1)O(1)。只使用到常数个变量。

参考：

LeetCode官方题解 - 92.反转链表II