题解 | #牛群的重新排列#

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param left int整型
     * @param right int整型
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int left, int right) {
        // write code here
        ListNode listNode = new ListNode(-1);
        listNode.next = head;
        ListNode rightNode = head;
        ListNode leftNode = listNode;
        for (int i = 0; i < left - 1; i++) {
            leftNode = leftNode.next;
        }
        for (int i = 0; i < right; i++) {
            rightNode = rightNode.next;
        }
        leftNode.next = reverseLinkedList(leftNode.next, rightNode);
        return listNode.next;
    }
    // 功能函数，翻转链表
    public ListNode reverseLinkedList(ListNode left, ListNode right) {
        // right相当于以前的null,以前翻转整个链表，自然是到尾巴，这次就到right
        ListNode prev = right;
        // 这里的left相当于以前的head，只不过这次的头并不一定是第一个节点
        ListNode curr = left;
        // 循环条件也要响应改变，以前是head!=null,这次同理，curr!=right,直到2,3,4这几个节点翻转完毕
        while (curr != right) {
            // 常规翻转链表操作，先记录后面一个结点，然后让指向前一个，然后地址赋值
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

本题知识点分析：

1.前驱结点和后继结点

2.链表遍历和结点赋值

本题解题思路分析：

1.和翻转链表一个道理，只不过这次是翻转区间链表，那我只要把头和尾给进去就了，原来翻转整个链表相当于头结点到null

2.leftNode相当于头结点 rightNode相当于第一个节点

3.让leftNode走到节点1的位置，rightNode走到节点4的位置

4.leftNode的下一个节点就是翻转2,3,4,这三个结点，也就是reverseLinkedList(leftNode.next,rightNode);

5.最后返回listNode.next,因为new 的listNode相当于一个虚拟头结点,.next相当于给出第一个真实节点的地址

本题使用编程语言: Java