面试算法-89-反转链表 II

题目

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

示例 1：

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

解

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null || left == right) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        int count = 1;
        ListNode pre = dummy;
        ListNode cur = head;
        ListNode next = null;

        ListNode p1 = null;
        ListNode p2 = null;
        ListNode p3 = null;
        ListNode p4 = null;
        while (cur != null) {
            next = cur.next;

            if (count == left) {
                p1 = pre;
                p2 = cur;
                pre.next = null;
            }
            if (count == right) {
                p3 = cur;
                p4 = next;
                cur.next = null;
            }
            count++;
            pre = cur;
            cur = next;
        }

        reverse(p2);
        if (p1 != null)
            p1.next = p3;
        p2.next = p4;
        return dummy.next;
    }

    public void reverse(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;

            cur.next = pre;

            pre = cur;
            cur = next;
        }
    }
}