[LeetCode] Reverse Linked List II 倒置链表之二

叁歲伎倆 2022-04-24 07:40 108阅读 0赞

本题是要对链表区间内的数据进行翻转，如下图所示。

![20190420152335243.jpg][]

如果是数组，知道起始位置m和终止位置n的下标，即可通过中间变量根据下标中心对称进行数据交换，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h6aGoyMDA3_size_16_color_FFFFFF_t_70][]

现在针对链表操作，无法直接对下标操作，只能根据地址指针对数据进行串联。假如是针对整个链表进行翻转，该如何思考呢，直观想法是开辟新的链表，然后原链表中的元素依次作为新链表的头结点，即如下所示。

![20190420151436545.png][]

Reverse Linked List II是针对链表区间进行翻转，此时针对整个链表翻转的思路依然可以借鉴，即每次将当前位置的元素移动到起始位置(m位置处)，为记录位置信息，针对原链表设置了两个变量，prev(m-1位的结点)和cur(m位的结点)，然后对其next值进行变量替换。

ListNode *reverseBetween(ListNode *head, int m, int n) {
            ListNode *dummy = new ListNode(-1), *pre = dummy;
            dummy->next = head;
            for (int i = 0; i < m - 1; ++i) pre = pre->next;
            ListNode *cur = pre->next;  //cur为m位置的元素
            for (int i = m; i < n; ++i) {
                ListNode *t = cur->next;  
                cur->next = t->next;      
                t->next = pre->next;      
                pre->next = t;      //变量替换，仅更新pre和cur的next值，不更新pre和cur结点的value值
            }
            return dummy->next;
        }

更一般的理解，就是对交换两个变量的值(pre->next, cur->next)，处理流程等同于相邻两结点交换的逻辑。

![20190420163248500.png][]

参考文献：

1.  [\[LeetCode\]链表倒置II][LeetCode_II]

[20190420152335243.jpg]: /images/20220217/aa6a664377954001a92a57b1bbb97b1d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h6aGoyMDA3_size_16_color_FFFFFF_t_70]: /images/20220217/7ca3301e8cf443be9586ed2ef852a1e3.png
[20190420151436545.png]: /images/20220217/a87f1f70e52d4f22a33749e0fbae3a30.png
[20190420163248500.png]: /images/20220217/10830489c6504adc99764eb34d2ed424.png
[LeetCode_II]: http://www.cnblogs.com/grandyang/p/4306611.html