[LeetCode] 92. Reverse Linked List II

佚名 4年前 (2020-02-14) 算法 677人围观抢沙发百度已收录

1. 原题链接：https://leetcode.com/problems/reverse-linked-list-ii/

2. 解题思路

采用头插法进行反转
利用哑节点将边界case转化为一般case

3. 算法

head2指针用于进行头插操作的头部指针
首先，将head2指针指向链表m-1的位置
然后，设置prev和cur指针遍历m到n-1位置的链表，依次对这些节点进行反转

4. 实现

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode dummy(-1);
        dummy.next = head;  //创建一个包含哑节点的链表
        
        //遍历到m-1的位置，当m为1时，此时哑节点就可以将这种边界case转化为一般case
        ListNode *prev = &dummy;
        for(int i = 0; i < m-1; i++){
            prev = prev->next;
        }
        ListNode * const head2 = prev;
        
        //采用头插法反转链表
        //反转至少需要两个节点，通过prev和cur两个节点实现反转
        prev = head2->next;
        ListNode *cur = prev->next;
        for(int i = m; i < n; i++){
            prev->next = cur->next;
            cur->next = head2->next;
            head2->next = cur;  //头插法
            cur = prev->next;
        }
        return dummy.next;
    }
};