【CodeTop 01】2024-07-03 - 92. 反转链表 II

[larscheng]

92. 反转链表 II

• 相似题：#137

[larscheng]

思路

• 头插法（穿针引线） 遍历链表节点，当进入反转区后，将后面的节点不断的往前移动，实现反转，这样可以只遍历一次，复杂度更低

代码

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1,head);
        ListNode pre = dummy;
        for (int i = 1; i < left; i++) {
            //反转区前一个节点
            pre = pre.next;
        }
        //依次遍历反转区元素，将反转区元素往前移
        //...[pre][cur][next]...--->....[pre][next][cur]....
        //cur.next=next.next,pre.next=next,next.next=cur
        ListNode cur = pre.next;
        ListNode next = null;
        for (int i = 0; i < right-left; i++) {
            //每次移位后cur和next的位置都会变化,pre不变
            next = cur.next;
            //移位
            cur.next = next.next;
            next.next = pre.next;//这里要用pre.next不能用cur，因为在移位的过程中cur会改变位置
            pre.next = next;
        }
        return dummy.next;
    }
}

复杂度

• 时间复杂度：O(n) 空间复杂度：O(1)