1.题目
2.思路
头插法，关键代码：
for(int i = 0; i < right - left; i++){ next = cur->next; cur->next = next->next; pre->next = next; next->next =cur; }
三个指针的顺序：pre，cur，next
（1）将cur的next指针指向next的下一个结点；
（2）把next的next指针指向pre的下一个结点；
（3）最后，把pre的next指针指向next结点。
就这样实现时间复杂度O ( n ) O(n)O(n)遍历一次链表，就将left到right的部分进行反转了。
3.代码（C++）
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode *DummyNode = new ListNode(-1);//惯用做法,防止left为1 DummyNode->next = head; ListNode *pre = DummyNode; for(int i = 0; i < left - 1; i++){//left从1开始的 pre = pre->next; } //pre到达要处理部分的前一个结点 ListNode *cur = pre->next; ListNode *next; for(int i = 0; i < right - left; i++){ next = cur->next; cur->next = next->next; next->next = pre->next;//最关键 pre->next = next; } return DummyNode->next; } };
4.代码（python）
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode: DummyNode = ListNode(-1) DummyNode.next = head pre = DummyNode for _ in range(left - 1): pre = pre.next cur = pre.next for _ in range(right - left): next = cur.next cur.next = next.next next.next = pre.next pre.next = next return DummyNode.next
