将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 &preview=true)
，空间复杂度 &preview=true)
。
例如：
给出的链表为
, 
,
返回
.
例如：
给出的链表为
返回
数据范围： 链表长度 
，
，链表中每个节点的值满足 
要求：时间复杂度 )
，空间复杂度
进阶：时间复杂度 ，空间复杂度 )
[编程题]链表内指定区间反转
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
struct ListNode *prev = NULL;
struct ListNode *next = NULL;
struct ListNode *phead = head;
struct ListNode *reverseBegin = NULL;
struct ListNode *reverseEnd = NULL;
int i = 1;
if (NULL == head || NULL == head->next || m >= n)
{
return head;
}
while(NULL != head)
{
if (i < m)
{
/* 记录翻转链表开始的地方 */
reverseBegin = head;
head = head->next;
}
/* 翻转链表结束后 */
else if (i > n)
{
head = head->next;
}
else {
if (i == m)
{
/* 翻转链表结束的地方是原翻转链表开头 */
reverseEnd = head;
}
/* 对需要翻转的节点进行翻转 */
next = head->next;
head->next = prev;
prev = head;
head = next;
/* 翻转链表最后一个节点时拼接前后的链表 */
if (i == n)
{
/* 考虑翻转链表从第一个结点开始 */
if (1 == m)
{
phead = prev;
/* 考虑翻转链表后面没有结点的情况 */
if (NULL != head)
{
reverseEnd->next = head;
}
}
else {
reverseBegin->next = prev;
reverseEnd->next = head;
}
}
}
i++;
}
return phead;
}
编辑于 2024-04-13 22:08:40
回复(0)
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
// write code here
if (head->next == NULL || head == NULL) {
return head;
} else if (m == n) {
return head;
}
struct ListNode* temp = NULL;
struct ListNode* prehead1 = NULL;
struct ListNode* prehead2 = NULL;
struct ListNode* prehead = NULL;
int i = 0, j = 0;
prehead = head;
while (i < m - 1) {
prehead1 = head;
head = head->next;
i++;
}
while (i < n) {
temp = head->next;
head->next = prehead2;
prehead2 = head;
head = temp;
i++;
}
if (prehead1 == NULL) {
prehead1 = prehead2;
while (prehead2->next != NULL) {
prehead2 = prehead2->next;
}
prehead2->next = temp;
return prehead1;
} else {
prehead1->next = prehead2;
}
while (prehead2->next != NULL) {
prehead2 = prehead2->next;
}
prehead2->next = temp;
return prehead;
}
发表于 2024-03-30 21:48:41
回复(0)
试错了好多次才写出来
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
// write code here
if(m==n) return head;
struct ListNode* p,*q,*r,*t;
struct ListNode *head2 = (struct ListNode*)malloc(sizeof(head));
r=head2;
int index=m;
head2->next=head;
for(int i=0;i<m-1;i++)
head2=head2->next;
p=head2->next;
t=head2->next;
head2->next=NULL;
while (index<=n&&p!=NULL) {
q=p;
p=p->next;
q->next=head2->next;
head2->next=q;
index++;
}
t->next=p;
return r->next;
}
编辑于 2024-03-20 17:00:56
回复(0)
struct ListNode* GetListNode(struct ListNode* head, int m) {
struct ListNode *p1;
p1 = head;
while(--m>0)
p1 = p1->next;
return p1;
}
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
struct ListNode *res, *buffer;
if(head == NULL || head->next == NULL || m==n)
return head;
if(m==1) {
int i,j;
for(i=0;i<n/2;i++) {
j = GetListNode(head,i+1)->val;
GetListNode(head,i+1)->val = GetListNode(head,n-i)->val;
GetListNode(head,n-i)->val = j;
}
return head;
}
res = reverseBetween(head, m, n-1);
buffer = GetListNode(head,n);
GetListNode(head,n-1)->next = buffer->next;
buffer->next = GetListNode(head,m);
GetListNode(head,m-1)->next = buffer;
return res;
}
编辑于 2024-03-13 20:09:42
回复(0)
struct ListNode* reverseBetween( struct ListNode* head, int m, int n) {
struct ListNode* prev = head;
struct ListNode* front = head;
struct ListNode* cur = head;
struct ListNode* next = head;
int a = m - 1;
int b = n - 1;
while (a--) {
prev = prev->next;
}
while (b--) {
cur = cur->next;
}
while (front && front->next != prev) {
front = front->next;
}
next = cur->next;
struct ListNode* temp1 = prev;
struct ListNode* pre = NULL;
while (prev != next) {
struct ListNode* temp = prev->next;
prev->next = pre;
pre = prev;
prev = temp;
}
if (front != NULL) {
temp1->next = next;
front->next = cur;
} else {
temp1->next = next;
head = cur;
}
return head;
}
编辑于 2024-02-11 18:24:26
回复(0)
struct ListNode* reverse(struct ListNode* head,struct ListNode* tail)
{
struct ListNode* phead = NULL;
struct ListNode* prev = head;
struct ListNode* cur = head->next;
struct ListNode* ptail = tail->next;
while(prev != tail)
{
prev->next = phead;
phead = prev;
prev = cur;
if(cur)
{
cur = cur->next;
}
}
prev->next = phead;
head->next = ptail;
return prev;
}
struct ListNode* reverseBetween(struct ListNode* head, int m, int n )
{
struct ListNode* pa = (struct ListNode*)malloc(sizeof(struct ListNode));
pa->next = head;
if(m == n)
{
return head;
}
else
{
struct ListNode* phead = head;
struct ListNode* pphead = head;
struct ListNode* cur1 = pa;
struct ListNode* cur2 = pa;
int i = 1;
int j = 1;
while(i < m)
{
cur1 = phead;
phead = phead->next;
i++;
}
while(j < n)
{
cur2 = pphead;
pphead = pphead->next;
j++;
}
if(m < n)
{
cur1->next = reverse(phead,pphead);
}
else
{
cur2->next = reverse(pphead,phead);
}
}
return pa->next;
}
发表于 2024-01-24 16:51:45
回复(0)
#include <stdlib.h>
struct ListNode* reverseBetween(struct ListNode* head, int m, int n )
{
typedef struct ListNode list;
//如果是从首节点开始反转，则没有上一个节点需要记录，所以需要创建一个首节点的上节点来保证程序正确。
list* empty =(list*)malloc(sizeof(list));
empty->val =0;
empty->next =head;
int i =0;
list* p1 =empty;
for(i=0;i<m-1;i++)
{
p1=p1->next;
}
//记录开始节点
list* start = p1->next;
list* new_node =start;
list* p2 =NULL;
for(i = m-1;i<n;i++)
{
list* tmp = new_node->next;
new_node->next =p2;
p2 =new_node;
new_node =tmp;
}
//链表反转结束，开始区间反转
p1->next =p2;
start->next = new_node;
//如果是从头反转，头节点不再是输入的节点
list* new_head =empty->next;
free(empty);
return new_head;
}
编辑于 2024-01-08 11:33:14
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @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 (!head || m == n) return head;
struct ListNode* cur = malloc(sizeof(struct ListNode));
cur->val = -1;
cur->next = head;
struct ListNode* res = cur;
for (int i = 0; i < m - 1; i++) {
res = res->next;
}
struct ListNode* now = res->next;
struct ListNode* next;
for (int i = 0; i < n - m; i++) {
next = now->next;//=next->next
now->next = next->next;
next->next = res->next;
res->next = next;//=now->next
}
return cur->next;
}
发表于 2023-12-14 22:31:56
回复(0)
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
int x = m;//记录起始位置
int c = n-m;//记录反转次数
if(c<=0 || head==NULL)//当不反转或空表时直接返回
{
return head;
}
struct ListNode* p = head; //用于记录区间前一个元素
struct ListNode* first = head; //用于记录区间第一个元素
if(x>1)//当区间外存在前一个元素时
{
while(m-2)//将p移动到区间前一个元素位置
{
p = p->next;
m--;
}
first = p->next;//移动到区间第一个位置
}
struct ListNode* left = first; //记录左边的元素（目标元素）
struct ListNode* right = first->next; //记录右边的元素（移动元素）
while(c)//反转次数
{
first->next = right->next;//使用区间第一个元素的next，记录移动元素下个元素的地址
right->next = left; //反向连接
left = right; //目标元素向右移动
right = first->next; //移动元素向右移动
c--;
}
if(x<=1)//当区间外不存在前一个元素时，头节点为left
{
return left;
}else {//存在前一个元素时，头节点为head
p->next = left;//前一个元素的next指向区间最后一个元素
return head;
}
}
编辑于 2023-12-14 09:44:25
回复(0)
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
// write code here
if(head == NULL || head->next==NULL ||m==n)
return head;
struct ListNode *new_head = (struct ListNode *)malloc(sizeof(struct ListNode)); //申请一个节点
if( new_head == NULL) //判断是否申请成功
return NULL;
new_head->next = head;//定义为新的头结点
struct ListNode *pHead = NULL;
struct ListNode *temp = NULL;
struct ListNode *pTail = NULL;
int i;
head = new_head;
for (i=0; i<m-1; i++) { //找到需要翻转节点的头一个节点
head = head->next;
}
pHead = head; //记录该节点
pTail = head->next; //记录尾节点，两边翻转完成后需要将后面未翻转的链表连接起来
head = head->next->next;//头插法反转链表
for (i=0; i<n-m; i++) {
temp = head;
head = head->next;
temp->next = pHead->next;
pHead->next = temp;
}
pTail->next = head;
return new_head->next;
}
发表于 2023-08-28 15:12:06
回复(0)
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
struct ListNode phead; //设置虚拟头结点
phead.next = head;
struct ListNode *next = NULL; //反转的下一个节点
struct ListNode *prior = NULL; //反转的前一个节点
struct ListNode *start = &phead; //反转链表第一个节点
struct ListNode *end = NULL; //反转链表最后一个节点
struct ListNode *left = NULL; //反转链表前的一个节点
struct ListNode *right = NULL; //反转链表后的一个节点
int i = 0;
for (i=0; i<m-1; ++i) //找到链表反转的前一个节点
{
start = start->next; //start的起始值：并不是整个链表的第一个节点
}
head = right = left = start->next; //链表反转的第一个节点
for (i=m; i<n; ++i) //找到链表反转的最后一个节点
{
right = right->next;
}
end = right->next; //反转链表结束后的节点
right->next = NULL; //将反转部分断开
while (head!=NULL)
{
next = head->next; //存储下一个节点
head->next = prior; //反转
prior = head; //存储前一个节点
head = next; //移到下一个节点
}
start->next = right; //将断开的链表接上
left->next = end; //将断开的链表接上
return phead.next;
}
编辑于 2023-12-17 16:11:42
回复(1)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @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 (head == NULL) return head;
if (m == n) return head;
struct ListNode* head1 = (struct ListNode*)malloc(sizeof(struct ListNode)); //创建一个虚拟头结点，连接链表，防止后续操作发生断错误
struct ListNode* p1 = head1;
head1->next = head;
struct ListNode* p2 = head;
for (int i = 1; i < m; i++) {
p1 = p2;
p2 = p2->next; //p2指向第一个需要调换的节点
}
for (int j = m; j < n; j++) {
struct ListNode* cur = p2->next; //指向第一个需要调换节点的下一个节点,永远是被摘下来的那个节点
p2->next = cur->next;
cur->next = p1->next;
p1->next = cur;
}
return head1->next;
}
发表于 2023-08-11 16:56:16
回复(1)
// https://note.youdao.com/s/FZhxKOmP 具体图示过程
#include <stdlib.h>
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
// write code here
struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* pre = NULL;
struct ListNode* cur = NULL;
struct ListNode* temp = NULL;
int i = 0;
newHead->next = head;
// 找到起始位置
pre = newHead;
for(i = 0; i < m - 1; i++)
{
pre = pre->next;
}
cur = pre->next;
for(i = 0; i < n - m; i++)
{
temp = cur->next;
cur->next = temp->next;
temp->next = pre->next;
pre->next = temp;
}
return newHead->next;
}
发表于 2023-08-04 15:59:27
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @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(head==NULL)
return NULL;
else if ((head->next==NULL) || (m == n))
return head;
else
{
// {1,2,3,4,5}
int i = 1;
struct ListNode* pHead1 = head;
struct ListNode* tmp = head;
struct ListNode* pHead1_end = m==1? NULL : head;
for(int i=1; i<m-1; i++)
{
pHead1_end = tmp->next;
tmp = tmp->next;
}
struct ListNode* pHead2 = (pHead1_end == NULL)? head:pHead1_end->next;
if(pHead1_end != NULL)
{
pHead1_end->next = NULL;
}
struct ListNode* x = NULL;
struct ListNode* tmp3 =pHead2;
// struct ListNode* pHead2_2 = pHead2;
for(int i=0; i<=n-m; i++)
{
pHead2 = pHead2->next;
tmp3->next = x;
x = tmp3;
tmp3 = pHead2;
}
if(pHead1_end != NULL)
{
pHead1_end->next = x;
}
else
{
head = x;
}
while (1)
{
if(x->next == NULL)
{
x->next = tmp3;
break;
}
x = x->next;
}
// x->next = tmp3;
return head;
}
}
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @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(head==NULL)
return NULL;
else if ((head->next==NULL) || (m == n))
return head;
else
{
// {1,2,3,4,5}
int i = 1;
struct ListNode* pHead1 = head;
struct ListNode* tmp = head;
struct ListNode* pHead1_end = m==1? NULL : head;
for(int i=1; i<m-1; i++)
{
pHead1_end = tmp->next;
tmp = tmp->next;
}
struct ListNode* pHead2 = (pHead1_end == NULL)? head:pHead1_end->next;
if(pHead1_end != NULL)
{
pHead1_end->next = NULL;
}
struct ListNode* x = NULL;
struct ListNode* tmp3 =pHead2;
// struct ListNode* pHead2_2 = pHead2;
for(int i=0; i<=n-m; i++)
{
pHead2 = pHead2->next;
tmp3->next = x;
x = tmp3;
tmp3 = pHead2;
}
if(pHead1_end != NULL)
{
pHead1_end->next = x;
}
else
{
head = x;
}
while (1)
{
if(x->next == NULL)
{
x->next = tmp3;
break;
}
x = x->next;
}
// x->next = tmp3;
return head;
}
}
发表于 2023-07-31 22:13:08
回复(0)
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
struct ListNode* pos;
struct ListNode* len;
struct ListNode* next1;
struct ListNode* temp;
struct ListNode* temp1;
struct ListNode* p = head;
struct ListNode* q = head;
struct ListNode* e = NULL;
struct ListNode*w;
if(m == n){
return head;
}
pos = head;
if(m>1){
for(int i = 0; i < m-1; ++i){
if(i == m-2){
w = pos;
}
pos = p->next;
p = pos;
}
}
for(int j =0; j < n-1; ++j){
len = q->next;
q = len;
}
temp = pos;
temp1 = len->next;
while (e!=len) {
next1 = temp->next;
temp->next = e;
e = temp;
temp = next1;
}
if(m==1){
pos->next = temp1;
return len;
}
pos->next = temp1;
w->next = len;
return head;
}
发表于 2023-07-21 20:18:19
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
