【原创】Leetcode -- Reverse Linked List II -- 代码随笔(备忘)

题目:Reverse Linked List II

题意:Reverse a linked list from position m to n. Do it in-place and in one-pass.

下面这段代码,有两个地方,一个是4、5行的dummy节点设置;另一个是11-14行,局部可视化到全局。

   ListNode *reverseBetween(ListNode *head, int m, int n) {
if(m == n) return head;
n -= m;
ListNode prehead();
prehead.next = head;
ListNode* pre = &prehead;
while(--m) pre = pre->next;
ListNode* pstart = pre->next;
while(n--)
{
ListNode *p = pstart->next;
pstart->next = p->next;
p->next = pre->next;
pre->next = p;
}
return prehead.next;
}

对于我,想记录的是第二点。

局部可视化到全局的意思是每一次局部指针调整要完成一个完整的链表转换。也就是说不应该根据全局来考虑单步情况,而是单步情况就完成一个全局的实现。

即: 1-2-3-4-5, m=2, n=4,  全局思想是 把2-4进行转换,再拼接到1-5中。局部思想是每一个单步都完成全局变化,不考虑n是多少。比如第一步在2处, 转换为1-3-2-4-5。

这里有两个好处,1:代码简洁,前中后三个指针可完成所有的交换。2:需要考虑的情况少,不用像全局思路分两步执行。3:可递归的执行。

上一篇:[LeetCode] 92. Reverse Linked List II 反向链表II


下一篇:[LeetCode] 163. Missing Ranges_Easy tag: array