92. Reverse Linked List II

题目链接

https://leetcode.com/problems/reverse-linked-list-ii/

代码

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        //先找出第m-1个节点，用pre表示
        m--;
        int cnt = 1;
        ListNode *pre = head;
        while (pre != NULL && cnt < m) {
            cnt++;
            pre = pre->next;
        }
        if (pre != NULL && pre->next != NULL && (m == 0 || pre->next->next != NULL)) {
            //cur表示当前转置的节点，nx表示下一个节点，tail表示转置子链表的末节点
            ListNode *cur, *nx, *t, *tail;
            if (m == 0) {
                //m就是第1个节点
                cur = head;
            } else {
                cur = pre->next;
                cnt++;
            }
            nx = cur->next;
            tail = cur;
            //转置
            while (nx != NULL && cnt < n) {
                cnt++;
                t = nx->next;
                nx->next = cur;
                cur = nx;
                nx = t;
            }
            //将转置的子链表连接上
            if (m == 0) {
                head = cur;
            } else {
                pre->next = cur;
            }
            tail->next = nx;
        }
        return head;
    }
};