92 反转链表 II
程序员文章站
2022-06-16 18:03:13
题目描述:反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明:1 ≤ m ≤ n ≤ 链表长度。示例:输入: 1->2->3->4->5->NULL, m = 2, n = 4输出: 1->4->3->2->5->NULL方法1:主要思路:(1)直观的想,找出要反转的一段的链表的头一个结点的前一个结点,使用头插法,将该段链表中的结点,按照要反转的个数,逐个的向后遍历,将各个结点插入到前面;(2)注意借助辅助的头结点;...
题目描述:
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
方法1:
主要思路:
(1)直观的想,找出要反转的一段的链表的头一个结点的前一个结点,使用头插法,将该段链表中的结点,按照要反转的个数,逐个的向后遍历,将各个结点插入到前面;
(2)注意借助辅助的头结点;
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode* dummy=new ListNode(0);//辅助的头结点
dummy->next=head;
ListNode* curNode=dummy;
//找出要反转的链表段的前一个结点
while(--m){
--n;
curNode=curNode->next;
}
//对当前段使用头插法进行反转
head=curNode;
curNode=curNode->next;
ListNode* tmpNode=NULL;
//使用要反转的个数作为限制
while(--n){
tmpNode=curNode->next;
curNode->next=tmpNode->next;
tmpNode->next=head->next;
head->next=tmpNode;
}
//释放内存
head=dummy->next;
delete dummy;
return head;
}
};
本文地址:https://blog.csdn.net/weixin_44171872/article/details/107286741