反轉指定區間的連結清單

class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }

    public ListNode(){}

}
  /**
     * @description 反轉指定位置的節點  [1,2,3,4,5]，start=2, end=4 -> [1,4,3,2,5]
     * @author HelloWorld
     * @create 2022/10/30 16:15
     * @param head
     * @param left
     * @param right
     * @return com.wy.leetcode.linkedlist.ListNode
     */
public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode cur = new ListNode();
        cur.next = head;

        // 1.先找到開始反轉定節點； 讓temp指向要開始反轉定節點， cur.next = temp;
        ListNode pre = cur;
        for (int i = 1; i < left; i++) {
            pre = pre.next;
        }
        head = pre.next;

        // 2.反轉
        // 反轉後的頭節點
        ListNode reversedHead = new ListNode();
        // 反轉後的頭節點的尾節點
        ListNode reversedTail = new ListNode();
        for (int i = left; i <= right ; i++) {
            ListNode temp = new ListNode(head.val);
            if (i == left) {
                reversedTail = temp;
            }
            temp.next = reversedHead;
            reversedHead = temp;

            head = head.next;
        }

        // 3.組裝
        pre.next = reversedHead;
        reversedTail.next = head;

        return cur.next;
    }