Solution1:
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* @brief 交换单链表数据域的值变相实现区间翻转,头指针后移,尾指针前移
* 但是单链表指针不能前移,时间复杂度O(n²),空间复杂度O(1)
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
// write code here
struct ListNode* front = head;
struct ListNode* tail = head;
for (int i = 1; i < m; i++)
{
front = front->next;
}
do
{
/*
*每次将tail指向head,再通过循环最后指向第n个结点,
*n每do循环一次减一,变相实现tail指针向前移动
*/
tail = head;
for(int j = 1; j < n; j++)
{
tail = tail->next;
}
int temp = front->val;
front->val = tail->val;
tail->val = temp;
front = front->next;
n--;
} while ((front < tail) && (front!=NULL) && (tail!=NULL));
return head;
}
Solution2:
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* @author Senky
* @date 2023.03.17
* @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
* @param pHead ListNode类
* @return ListNode类
*/
#include <stdio.h>
struct ListNode* ReverseList(struct ListNode* pHead ) {
// write code here
struct ListNode* prev = NULL;
struct ListNode* curr = pHead;
struct ListNode* next;
//退出循环后curr指向NULL
while(curr != NULL)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* @brief
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
// write code here
if(m != n)//m、n不等于才需要翻转链表
{
struct ListNode* front = head;
struct ListNode* front_pre = NULL;//初始化默认m无前驱
/*m有前驱结点*/
if(1 != m)
{
front_pre = head;
front = front->next;
/*将front定位在第m个结点处*/
for (int i = 2; i < m; i++)
{
front = front->next;
front_pre = front_pre->next;
}
}
/*将tail定位在第n个结点处
*此时的n必定大于2
*/
struct ListNode* tail = head;
struct ListNode* tail_next = NULL;//初始化默认n无后继
/*将tail定位在第n个结点处*/
for (int j = 1; j < n; j++)
{
tail = tail->next;
}
if(tail->next != NULL)
{
tail_next = tail->next;//有后继
}
/*将tail和tail_next断开,那么区间链表只有front到tail
*同时front_pre和tail_next记录了区间链表的前驱和后继(如果有)
*/
tail->next = NULL;
/*
* 链表头:head
* 区间表头:tail
* 区间表尾:front
*(1)front有前驱:
*则head是链表头,区间翻转后需要用front_pre指向区间链表头结点
* (1')tail有后继
* 区间翻转后需要用区间表尾front指向tail_next
* (1'')tail无后继
* 区间翻转后需要用区间表尾front指向tail_next(无后继tail_next为空)
*(2)front无前驱:
*则区间链表头tail是整个链表头,将head指向区间链表头结点
* (2')tail有后继
* 区间翻转后需要用区间表尾front指向tail_next
* (2'')tail无后继
* 区间翻转后需要用区间表尾front指向tail_next(无后继tail_next为空)
*/
if(front_pre != NULL)
{
front_pre->next = ReverseList(front);//(1)front有前驱
}
else
{
head = ReverseList(front);//(2)front无前驱
}
front->next = tail_next;
}
return head;
}
Solution2图解:
