题解 | #调整牛群顺序#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param n int整型 
 * @return ListNode类
 */
#include <stdio.h>
struct ListNode* moveNthToEnd(struct ListNode* head, int n ) {
    // write code here
    if(head==NULL || n == 1) return head;
    //获取链表长度，倒数第n个，cur从第二个位置需要循环len-n-1次找到该节点
    struct ListNode *t = head,*pre = NULL,*cur=head;
    int len = 0;
    while(t)
    {
        len++;
        t = t->next;
    }
    //对于第一个元素做特殊处理
    if(len==n)
    {
        pre = cur->next;
        head = pre;
    }
    else {
        for(int i=0;i<len-n;i++)
        {
            pre = cur;
            cur = cur->next;
        }
        pre->next = cur->next;
    }
    //将cur运动到倒数第n个数字的位置，pre为前一个
    cur->next = NULL;
    //改变链表顺序
    while(pre->next)
    {
        pre=pre->next;
    }
    pre->next = cur;
    return head;
}

1.考察的知识点：单链表

2.编程语言：C

3.解题思路

首先定义一个cur指针用来找到需要改变顺序的位置，此时需要确定链表长度len；

pre先指向NULL，cur指向head，然后向后移动len-n个位置即可

此时断开cur前面的指针，pre->next = cur->next；

将cur与后面的链表断开，cur->next = NULL；

然后根据边界条件pre->next存在；

pre向后找到尾节点，尾节点指向cur，返回head即可。

针对n==len的特殊情况，首先将pre和head都指向第二个元素，同理改变指针指向即可