LeetCode 92 反转链表2

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    /**
    	想到两种方法：
    		- 一种先把[left, right]间的值放到数组里，反转数组，然后再遍历链表，
    		将反转后的值赋回链表节点
    		- 保存几个特殊的节点值：头结点、left节点的前一个节点、left节点、right节点、
    		right节点的后一个节点。期间记录下链表的长度，并把记录下的right节点的后一个节
    		点赋为null，调用反转单链表的函数，传入left节点，不需要返回值。然后拼接时注意
                几种特殊情况即可。
    		
    	下面只编写第二种方法
     */
public class ReverseList2 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null|| head.next == null || left == right)
            return head;

        ListNode tempHead = head;
        ListNode preLeft = tempHead;
        for (int i = 0; i < left - 1; i++) {
            preLeft = tempHead;
            tempHead = tempHead.next;
        }
        ListNode leftHead = tempHead;

        ListNode tempLH = leftHead;
        ListNode rightTail = leftHead;
        for (int i = 0; i < right - left + 1; i++) {
            rightTail = tempLH;
            tempLH = tempLH.next;
        }
        ListNode beRight = tempLH;

        int cnt = right;
        while (tempLH != null) {
            tempLH = tempLH.next;
            cnt++;
        }

        rightTail.next = null;

        reverseList(leftHead);

        if (left == 1 && right != cnt) {
            head.next = beRight;
            head = rightTail;
        }
        else if (left != 1 && right == cnt) {
            preLeft.next = rightTail;
            leftHead.next = null;
        }
        else if (left == 1 && right == cnt) {
            return rightTail;
        }
        else {
            preLeft.next = rightTail;
            leftHead.next = beRight;
        }
        return head;

    }

    private void reverseList(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = newHead;
            newHead = head;
            head = next;
        }
    }

    public static void main(String[] args) throws IOException {
        ListNode head = null;
        ListNode tempHead = null;
        BufferedReader br = new BufferedReader(newInputStreamReader(System.in));
        String numS = br.readLine();
        String[] nums = numS.trim().split(" ");
        for (int i = 0; i < nums.length; i++) {
            ListNode temp = new ListNode();
            temp.val = Integer.parseInt(nums[i]);
            temp.next = null;
            if (head == null) {
                head = temp;
                tempHead = head;
            }
            else {
                head.next = temp;
                head = head.next;
            }
        }
        numS = br.readLine();
        nums = numS.trim().split(" ");
        int left = Integer.parseInt(nums[0]);
        int right = Integer.parseInt(nums[1]);
        ReverseList2 rl = new ReverseList2();
        head = rl.reverseBetween(tempHead, left, right);
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
}

LeetCode 92 反转链表2

原文：https://www.cnblogs.com/easternE/p/14617103.html