反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL


/*
 * @lc app=leetcode.cn id=92 lang=cpp
 *
 * [92] 反转链表 II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void printList(ListNode* head) {
        ListNode* cur = head;
        printf("list: %d ", cur->val);
        while(cur->next != NULL) {
            cur = cur->next;
            printf("%d ", cur->val);
        }
        printf("\n");
    }
    ListNode* reverse(ListNode* head, int count) {
        // printList(head);

        ListNode* cur = head;
        ListNode* curNew = NULL;
        ListNode** ptr = &curNew;

        int times = 0;
        while(cur) {
            ListNode* tmp = cur->next;
            cur->next = curNew;
            curNew = cur;
            cur = tmp;

            times++;
            if(times > count) { //找到反转链表结束位置
                // printf("cur %d\n", cur->val);
                head->next = cur;
                break;
            }
        }
        // printList(curNew);
        return curNew;
    }

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* cur = head;
        ListNode* curNew = NULL;

        if (m > 1) {
　　　　　　　 // 找到m-1位置的节点
            for(int i = 1; i< m; i++) {
                curNew = cur;
                cur = cur->next;
            }
　　　　　　　 // m-1 的节点的next指向反转链表
            curNew->next = reverse(cur, n - m);
            return head;
        } else {
            return reverse(cur, n - m);
        }
    }
};
// @lc code=end

 

版权声明：本文为superPerfect原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/superPerfect/p/13068683.html