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

考察知识点：链表、链表旋转、链表遍历

解题分析：

首先可以将整个链表分为三部分（一般情况下），第一部分是需要旋转的链表前部，第二部分是旋转的链表，第三部分是需要旋转的后部，解题流程如下

1、首先便利出需要旋转的链表的前部，这部分保持不变，并保存left值前一个元素的地址在left_head中

2、之后的内容都是旋转的部分，这部分的操作就是将该部分重新组合成新的链表，并保存到new_head中；其中每获取一个新的链表成员，都将该成员插入到new_head的前部，并刷新new_head为新插入值的地址。（值得注意的是，这里需要保存new_head的第一个元素，因为这个元素是旋转后链表的末尾地址，保存在指针end_head中）

3、当遍历完成需要旋转的链表内容后，也就是遍历到right+1个成员后，就可以结束循环了，当前的right成员就是旋转链表需要旋转的最后一个成员，也就是新组成链表的最开始一个成员；结束循环后，就将旋转后新的链表的链表头new_head拼接到left_head->next上，之后将新链表的的链表最后一个成员的地址指向right当前成员的下一个成员

编程语言：C

完整的编码代码：如下所示：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param left int整型 
 * @param right int整型 
 * @return ListNode类
 */
#include <stdbool.h>
struct ListNode* reverseBetween(struct ListNode* head, int left, int right ) {
    struct ListNode *tmp_head = head;
    struct ListNode *left_head = NULL, *end_head = NULL;
    struct ListNode *new_head = NULL, *next_head = NULL;
    int count = 1;
    bool flag = false;

    while (1) {
        if (count == (left-1)) {	//找到了需要旋转链表内容的前部分
            left_head = tmp_head;
            tmp_head = tmp_head->next;
        } else if (count == (right+1) || tmp_head == NULL) {	// 找到了需要旋转链表内容的后部分
            end_head->next = tmp_head;		// 将新链表的最后一个成员的下一个地址指向需要旋转链表内容的链表后部
            if (left_head == NULL)
                head = new_head;	//如果链表前部没有找到，那就需要旋转的第一个成员就是原链表的第一个成员，可以不用拼接链表前部
            else
                left_head->next = new_head;		//将新链表拼接到找到的需要旋转链表的链表前部
            break;
        } else if (count >= left && count <= right) {	//在这个取值范围内的链表成员都需要旋转，组成新的链表new_head
            next_head = tmp_head->next;		//保存原链表中的下一个成员的地址
            if (new_head == NULL) {		//如果新链表没有初始化的话，就初始化链表的第一个车成员
                new_head = tmp_head;
                new_head->next = NULL;		//将新链表的最后一个成员的next指针赋空，防止出错
                end_head = new_head;	//标记新链表的最后一个成员
            } else {
                tmp_head->next = new_head;		// 向新链表中的前面增加一个链表成员
                new_head = tmp_head;
            }

            tmp_head = next_head;	//刷新当前成员为原列表的下一个成员
            next_head = NULL;
        } else if (tmp_head != NULL) {
            tmp_head = tmp_head->next;		// 如果count的值不是以上的任何一种情况，就刷新当前值为下一个成员的地址
        }

        count++;
    }

    return head;
}