算法练习(13) - 反转链表中间某段

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

答案

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode g  = dummyHead;
        ListNode p  = dummyHead;

        for(int i =0;i<left-1;i++){
            g = g.next;
            p = p.next;
        }
        p = p.next;

        for(int i = left;i < right;i++){
            // 将p的next缓存一下
            ListNode removed = p.next;
            // p一直在left节点上,指向next.next
            p.next = p.next.next;
            // 将缓存值头插到g.next
            removed.next = g.next;
            // 将缓存值尾插到g
            g.next = removed;
        }
        return dummyHead.next;
    }
}

思路

如图 :

先将指针 p ,g 同时移动到 left前节点

再把p指针后移一位到left节点

以p节点为中间点,将p后边的节点头插到p节点和g节点之间;