先解释一下这个题,就是指定一个范围,把这个范围内的数反转。比如2->1->5->4->3->null
,反转(2,4):2->4->5->1->3->null
。
首先是要注意限制,那么如果表为空,返回self;而数字上的限制,因为已经说明:
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
所以不用考虑m>n啊之类的问题。于是只用控制一个量,就是m==n,因为m到结尾也最多是m==n,不需要做太多控制。
代码如下:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if(head == nullptr || m==n)
return head;
//快速创建一个,设为0,next指向原链表
ListNode *newList = new ListNode(0);
newList->next = head;
ListNode *pre = newList;
for(int i = 1; i < m; ++i)
pre = pre->next;
ListNode *cur = pre->next;
ListNode *tmp = nullptr;
for(int i = 0; i< n - m; ++i) {
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return newList->next;
}
我们可以看出,反转链表的核心操作都是中间那4句话,i.e.,后边的指向后边,当前后边的指向前边,前边的指向当前,当前指向后边。
网友评论