引入哑节点,先反转子链表,再连接:
// // Created by jt on 2020/9/24. // class Solution { public: /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ ListNode* reverseBetween(ListNode* head, int m, int n) { // write code here ListNode *pre, *post; // 分别保存子链的前一个节点和子链的后一个节点 ListNode *begin, *end; // 分别保存子链的第一个节点和子链的最后一个节点 ListNode dummy(0); dummy.next = head; ListNode *p = &dummy; int cnt = 0; while (cnt <= n) { if (cnt+1 == m) { pre = p; begin = p->next; } if (cnt == n) { end = p; post = p->next; } ++cnt; p = p->next; } // 断链并反转 ListNode *q = begin; // 保存反序后的头 p = begin->next; while (p != post) { ListNode *tmp = p->next; p->next = q; q = p; p = tmp; } // 重新合链 pre->next = end; begin->next = post; return dummy.next; } };