题目:
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
其实,看到这个题,我的想法是直接反转中间那块。看起来挺简单,思路也没有问题。直接做就OK了。其实,是错误的;看到链表的题,应该先脑袋里过下什么是链表,链表是干嘛的。
这道题,很清晰。
直接分成三段,前后不用管,直接反转中间部分即可。
于是,有了下面的答案。参考代码:
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
// 设置 dummyNode 是这一类问题的一般做法
ListNode *dummyNode = new ListNode(-1);
dummyNode->next = head;
ListNode *pre = dummyNode;
///链表向后移动left个,然后分割出第一个链表左边部分。
for (int i = 0; i < left - 1; i++) {
pre = pre->next;
}
ListNode *cur = pre->next;
ListNode *next;
///中间部分,直接反转。
for (int i = 0; i < right - left; i++) {
next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
///返回结果
return dummyNode->next;
}
};
网友评论