LeetCode Daily Question 24

May 7th 2022

5 月 7 日 每日一题

题目：284. Peeking Iterator

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

1
2
3
4
5
6
Example 1:
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Example 2:
Input: head = [5], left = 1, right = 1
Output: [5]

思路

I. Dummy Node
用于避免 reverse 的 left 为 head 的 edge case，结束时返回 dummy node 的 next 即可。

II. 移动指针，将指针指向 left，并且需要记录 left 的前一个 node，以便结束时 connect。需要注意的是循环的运行次数应该为 left - 1.

III. 对要求区域进行 reverse，需要记录 curr，prev 和 forwarding，流程为，首先记录 current node 的 next，然后将 current node 的 next 指向 prev，然后将 prev 更新为 current node，current node 更新为 forwarding node。reverse 的次数为 right - left + 1，这是因为第一次循环 prev 为 nullptr。

IV. 连接 reverse 区域与其余区域，此时 current 指向 node after right，并且 leftPrev 的 next 为 reverse 前的 left。首先将 reverse 前的 left 的 next 指向 current。然后将 leftPrev 的 next 指向 prev（right）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(left == right)
            return head;
        //dummy node
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        //go to left
        ListNode *leftPrev = dummy;
        ListNode *cur = dummy->next;
        for(int i = 0; i < left - 1; i++){
            leftPrev = cur;
            cur = cur->next;
        }//now cur points to left
        //reverse from left to right
        ListNode* prev = nullptr;
        for(int i = left; i < right + 1; i++){
            ListNode* forwarding = cur->next;
            cur->next = prev;
            prev = cur;
            cur = forwarding;
        }
        //connect
        leftPrev->next->next = cur;
        leftPrev->next = prev;
        return dummy->next;
    }
};

,
  1. 5 月 7 日 每日一题
    1. 题目：284. Peeking Iterator
    2. 思路
    3. 代码