题解 | #链表内指定区间反转#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

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* dumy = new ListNode(0);
        dumy->next = head;
	  // 假设 节点长这样: p,a,b,c,d,q
	  // 1.找到p和q
        ListNode* p = dumy;
        for (int i = 0; i < m - 1; i ++) p = p->next;
        ListNode* q = dumy;
        for (int i = 0; i < n; i ++) q = q->next;
        
	  // 2.每次都p后面的节点放到d屁股后面
        for (int i = 0; i < n - m; i ++) {
            ListNode* take = p->next;
            p->next = take->next;
            take->next = q->next;
            q->next = take;
            show(dumy->next);
        }
        return dumy->next;
    }
    void show(ListNode* head) {
        ListNode* p = head;
        while (p) {
            printf("%d ", p->val);
            p = p->next;
        }
        printf("\n");
    }
};