欢迎访问LeetCode题解合集
题目描述
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
题解:
将链表分成三部分,1~m-1
、m~n
和 n+1~最后
。可以分三步走完成:
- 找到第
m-1
个节点,设为s
; - 将第
m~n
个节点反转; - 将三部分拼接起来:即
m->next = n->next; s->next = n;
。
时间复杂度:$O(n)$
额外空间复杂度:$O(1)$
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if ( m == n ) return head;
ListNode *dummy = new ListNode;
dummy->next = head;
ListNode *p = dummy;
for ( int i = 1; i < m; ++i ) p = p->next;
ListNode *pre = p->next, *next = nullptr, *now = pre->next;
for ( int i = m; i < n; ++i ) {
next = now->next;
now->next = pre;
pre = now;
now = next;
}
p->next->next = now;
p->next = pre;
return dummy->next;
}
};
/*
时间:0ms,击败:100.00%
内存:7.2MB,击败:19.00%
*/