反转链表、反转链表II

反转链表

题目链接： AcWing 35. 反转链表
关键词： 链表

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

思考题：

请同时实现迭代版本和递归版本。
样例

输入:1->2->3->4->5->NULL输出:5->4->3->2->1->NULL


迭代版本：

迭代版本是员工思维：我该如何实现

迭代版本用循环来实现：
首先将a赋为头结点head，b是a->next；
每次只要b不为空，就让b-> next = a，然后a、b往后移一位，c用来存放b原本的后一位；
注意：别忘了让头结点指向NULL；
最后返回反转后链表的头结点，也就是a

代码实现：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head || !head->next) return head; //为空或者只有一个结点就直接返回auto a = head, b = head->next;while(b){ auto c = b->next;b->next = a;a = b, b = c;}head->next = NULL;return a;}
};


递归版本：

递归版本是老板思维：我该怎么让下面的人实现。

反转整个链表，可以想成递归处理当前结点之后的那部分链表；
当前结点head之后的链表递归完成之后该怎么处理呢？
head的下一个结点指向head，然后head指向空就行了

代码实现：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head || !head->next) return head;auto tail = reverseList(head->next);head->next->next = head;head->next = NULL;return tail;}
};


反转链表II

题目链接：Leetcode 92. 反转链表 II
关键词： 链表

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

实例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

分析：

其实就是先移动到left，然后用迭代的方式反转从left到right之间的部分链表。

• a 移动到left之前的位置
• 循环right - left次，每次都让c指向b，然后b和c往后移动一位（d用来存储c原本的后一位）
• 循环结束时，b就到了right的位置，c就到了right的后一位。让a指向b，a的下一位的指向c就行了
• 最后返回头结点

注意： left可能从头开始，因此头结点可能变，也可能不变。最好的方法是建立一个虚拟头结点dummy，它指向真实的头结点。最后返回dummy->next就可以了。

代码实现：

/*** 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) {auto dummy = new ListNode(-1);dummy->next = head;auto a = dummy;for(int i = 0; i < left - 1; i ++ ) a = a->next;auto b = a->next, c = b->next;for(int i = 0; i < right - left; i ++ ){ auto d = c->next;c->next = b;b = c, c = d;}a->next->next = c;a->next = b;return dummy->next;}
};