LeetCode: 92. Reverse Linked List II

题目描述

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

题目大意: 将给定链表的指定区间倒置。

解题思路

  1. 递归求解: reverseBetween(head, m, n) 相当于将 head->next 的 [m-1, n-1] 区间的节点进行倒置(reverseBetween(head->next, m-1, n-1)).
  2. 经过递归操作后，实际上需要处理的问题变成 reverseBetween(head, 1, n) 形式，即，将链表的前 n 个节点倒置。
    此时，只需要遍历前 n 个节点, 并用 头插法 重新插入链表即可。

AC代码

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // 1 ≤ m ≤ n ≤ length
        if(m > 1)
        {
            head->next = reverseBetween(head->next, m-1, n-1);
            return head;
        }

        ListNode* reversePartHead = head;
        ListNode* reversePartTail = head;
        ListNode* nonReversePartHead = head->next;

        // reverse first n node.(头插法)
        while(--n)
        {
            ListNode* tmp = nonReversePartHead;
            nonReversePartHead = nonReversePartHead->next;

            tmp->next = reversePartHead;
            reversePartHead = tmp;
        }

        reversePartTail->next = nonReversePartHead;

        return reversePartHead;
    }
};