反转链表，给你单链表的头指针 head 和两个整数 left 和 right

Question

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

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

Answer 1

一、思路

首先找到对应那一段，然后截断后作为单独的链表，进行翻转。
再把之前的链表和那个单独链表接起来即可。

二、源码

struct ListNode* reverseList(struct ListNode *l) {
    struct ListNode *pre = l, *now = l->next;
    struct ListNode *head = l;
    while(now) {
        pre->next = now->next;       // (1) 将 now 从链表中剥离出来；
        now->next = head;            // (2) 将 now 插入到之前的链表头之前；
        head = now;                  // (3) 让 now 成为新的链表头；
        
        now = pre->next;             // (4) now 也前进一格；
    }
    return head;
}


struct ListNode* reverseBetween(struct ListNode* head, int left, int right){
    struct ListNode *now = head, *pre = NULL;
    struct ListNode *prel = NULL, *l, *r, *rnext;
    int cnt = 0;
    if(left == right) {
        return head;
    }
    while(now) {
        ++cnt;
        if(cnt == left) {
            prel = pre;
            l = now;
        }
        if(cnt == right) {
            r = now;
        }

        pre = now;
        now = now->next;
    }
    rnext = r->next;
    r->next = NULL;
    reverseList(l);
    l->next = rnext;

    if(prel) {
        prel->next = r;
    }else {
        head = r;
    }
    return head;
}