链表 练习

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。   数据范围： 0\leq n\leq10000≤n≤1000 要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。   如当输入链表{1,2,3}时， 经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。 /**  * struct ListNode {  *  int val;  *  struct ListNode *next;  * };  *  * C语言声明定义全局变量请加上static，防止重复定义  */   /**  *  * @param pHead ListNode类  * @return ListNode类  */ struct ListNode* ReverseList(struct ListNode* pHead ) {     // write code here     if(pHead == NULL)     {         return NULL;     }     if(pHead->next == NULL)     {         return pHead;     }     struct ListNode* p = pHead;     struct ListNode* pnext = pHead->next;     p->next = NULL;     while(pnext)     {         struct ListNode* ptmp = pnext->next;         pnext->next = p;//2->1         p = pnext;//12--23         pnext = ptmp;//12--23     }     return p; } 将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
例如：
给出的链表为 1\to 2 \to 3 \to 4 \to 5 \to NULL1→2→3→4→5→NULL, m=2,n=4m=2,n=4,
返回 1\to 4\to 3\to 2\to 5\to NULL1→4→3→2→5→NULL.

数据范围： 链表长度 0 < size \le 10000<size≤1000，0 < m \le n \le size0<m≤n≤size，链表中每个节点的值满足 |val| \le 1000∣val∣≤1000  

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* p2s;
struct ListNode* plast = NULL;
struct ListNode* p1s;
struct ListNode* pnext;
int i ;
p->next = head;
if(m == n)
{
return head;
}
for(i = 0;i {
p1s = p;//反转节点的前一个结点
p = p->next;//p在要反转的节点
}
p2s = p;//反转节点 ， 成为尾节点

for( i = 0;i<=n-m;i++)
{
pnext = p->next;//存储要滑动的节点
p->next = plast;//反向链接
plast = p;//存储上一节点
p = pnext;//滑动
}
if(p!=NULL)
{
p2s->next = p;//链接新尾部
}

p1s->next = plast;
if(((i == 2)&&(m == 1))||(i == n))//特色case：相邻变化;头尾全变化
{
return plast;
}
return head;
// write code here
}