题目概要

将指定范围内的链表翻转。

题目链接

Reverse Linked List II

题目解析

注意，题目中标注了条件：$1\le m \le n \le length_of_list$
我们现在来关注翻转某局部链表时，所需要进行的操作：

 [+]->[+]->[o]->[o]->[o]->[o]->[o]->[x]->[+]->[+]->^
       ^                        ^    ^
       |                        |    |
      tail                 revTail revHead

上图中[+]表示的结点为正常结点，而[o]为已经被翻转过的链表结点，[x]为正在被翻转的结点。
易知此时需要进行的操作如下：

revHead = revTail->next;
revTail->next = revHead->next;
revHead->next = tail->next;
tail->next = revHead;

之后，上述链表将变为如下图所示形式：

 [+]->[+]->[x]->[o]->[o]->[o]->[o]->[o]->[+]->[+]->^
       ^    ^                        ^
       |    |                        |
      tail revHead                revTail

如此反复多次，准确的说是$n-m$次后，就可以完成翻转了。
同时还需要注意的是$m==1$的情形。

复杂度分析

时间复杂度：$O(n)$
空间复杂度：$O(1)$

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
private:
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* newHead = new ListNode(0);
        newHead->next = head;
        ListNode* tail = newHead;
        for (int i=0; i<m-1; ++i)
            tail = tail->next;
        ListNode* revTail = tail->next;
        ListNode* revHead = NULL;
        for (int i=0; i<n-m; ++i) {
            revHead = revTail->next;
            revTail->next = revHead->next;
            revHead->next = tail->next;
            tail->next = revHead;
        }
        // delete the pointer
        ListNode* toDelete = newHead;
        delete toDelete;
        newHead = newHead->next;
        return newHead;
    }
};

广告区域

本人和小伙伴们承接各种软件项目，有需求的可以联系我们。
QQ: 2992073083