day4--链表内指定区间反转

迭代方法

1. 第m个节点的前一个节点pre和第n个节点；

2. 将第m个节点到第n个节点的链表部分反转；

3. 将pre节点的next指向反转后链表的头节点，将反转后链表的尾节点的next指向n+1节点。

/*** struct ListNode {*	int val;*	struct ListNode *next;* };*/#include <bits/types/struct_tm.h>
#include <cstddef>
class Solution {
public:/*** * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类*/ListNode* reverseBetween(ListNode* head, int m, int n) {// write code hereListNode *new_head=new ListNode(-1);//设置虚拟头节点ListNode *start, *tmp, *phead;new_head->next=head;//找到区间左端点phead=new_head;start=head;//start从第一个元素开始for(int i=1; i<m; i++){phead=start;start=start->next;}for(int j=1; j<=n-m; j++){tmp=start->next;start->next=tmp->next;tmp->next=phead->next;phead->next=tmp;}return new_head->next;}
};

设置虚拟头结点的作用

1. 简化链表操作

在链表操作中，如果不使用虚拟头结点，我们需要针对头节点和其他节点分别进行操作，这会导致代码的重复和冗余。而设置虚拟头结点后，我们可以将头节点和其他节点一视同仁，从而简化链表操作的实现。

2. 处理边界情况

当链表为空时，我们需要特殊处理头节点。如果使用虚拟头结点，我们可以省去这个特判，因为虚拟头结点始终存在。

3. 方便删除操作

在链表中，删除头节点时需要特殊处理。如果使用虚拟头结点，我们可以将虚拟头结点作为头节点的前一个节点，从而将删除头节点的操作转化为删除第二个节点的操作，避免了特判。

4. 方便插入操作

在链表中，插入头节点时需要特殊处理。如果使用虚拟头结点，我们可以将虚拟头结点作为头节点的前一个节点，从而将插入头节点的操作转化为插入第二个节点的操作，避免了特判。

综上所述，设置虚拟头结点可以简化链表操作的实现，同时可以避免特判和处理边界情况的麻烦。因此，在链表操作中，设置虚拟头结点是一个常见的技巧。