链表反转问题详解

链表反转类问题是链表问题中比较典型的问题，具有一定的难度，本文将会进行详细讲解

---

---

前言

提示：这里可以添加本文要记录的大概内容：

链表是数据结构中的一种线性数据结构，它的结构可以理解为一个结构体，内部存储着一个值和其对下一个链表的指向。
链表的种类很多，主要有单链表（本文所有题目都是讲解单链表），双链表，循环链表，他们的结构大同小异，都是类似的结构体指向，只是单链表只有一个指针，双链表存在两个 两个指针，循环链表的尾结点指向不同

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、整个链表反转

整个链表反转即为链表的结点全部反转过来，比如1->2->3->4，变成4->3->2->1，这种形式即为整个链表反转，主要可以采用栈，头插法，递归，三指针法三种方法

1.栈

void reverseLinklist(Linklist L)
{stack<Integer> stk = new Stack<>();//定义栈Linklist p = L->next;while (p)  //依次读取栈的内容{stk.push(p->data);p = p->next;}p = L->next;while (p)   //依次出栈，更换链表中的数据{p->data = stk.top();stk.pop();p = p->next;}
}

使用栈来进行存储的话往往是只进行数据交换

2.头插法

头插，意思就是把结点依次放到头节点的下一个位置，当每个结点都一一放到头结点后面就可以实现反转

代码如下（示例）：

void reverseLinklist(Linklist& L)  //头插法实现链表的反转
{Linklist p = new Linklist();			//用于记录p接下来的位置 Linklist r = new Linklist();			//记录p的位置进行头插p = L->next;		//用p来记录头节点以后的内容L->next = NULL;		//先将链表的头节点置空while (p){r = p;			//用r来记录当前p的位置p = p->next;    //用p来不断地进行查找下一个元素r->next = L->next; //进行头插L->next = r;}
}

3.递归

图片:

代码如下（示例）：

Linklist reverseLinklist(Linklist& L)
{if (L == NULL || L->next == NULL){return L;}else{Linklist newHead = reverseLinklist(L->next);L->next->next = L;L->next = NULL;return newHead;}
}

注意事项：

递归的时候无法删除头节点，所以递归法适合用于没有头节点的链表的反转，这也是递归法的一个弊端;
要用新的头节点记录最后一个节点的位置，所以在找到该节点后要通过函数来返回该节点，即代码中的 newHead;
反转的操作：L->next->next = L, 这里说明一下：L->next 是下一个指针，而L->next->next 是下一个指针的指向，所以让下一个指针的指向来指向当前指针，从而实现反转。
最后还要令L->next = NULL, 即切断原来正向的指向。
空间复杂度为O(n), 时间复杂度为O(n)

4.三指针法

三指针：
Linklist cur : 记录当前的节点;
Linklist pre : 记录当前节点的上一个节点;
Linklist r : 记录当前节点的下一个节点（即剩下的节点）;
图片:
代码示例如下

void reverseLinklist(Linklist& L) //三指针法实现链表的反转
{Linklist pre = new Linklist();	// 记录之前的结点Linklist cur = new Linklist();	// 记录当前的结点Linklist r = new Linklist();		// 记录剩下的结点pre = NULL;		 //要先pre指针置为空cur = L->next;   //指向第一个结点while (cur){r = cur->next;  //这样r不会成为野指针,且这一步一定要在最前面。即当cur不为空的时候才指向下一个cur->next = pre; //转方向pre = cur;      //往后移cur = r;}//结束后cur为空，所以L->next要指向pre;L->next = pre;
}

以上部分参考链接: 链接: link，本人可能讲得不足，大家可以前往查看原文

示例

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：

输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]

代码如下：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode pre,cur,next;pre = null;cur = head;while(cur != null){next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}
}

二.反转部分链表结点

在实际问题中，经常存在的往往是反转部分链表问题，此类问题需要在反转所有链表的基础上往往需要增加区间的判断

1.思路分析

部分链表反转问题主要可以分为三步：
1.先确定区间的范围
2.将区间进行反转
3.将反转后的区间进行拼接
注意事项：往往在头结点前插入一个虚拟头结点，防止区间进行反转影响指向

2.例题

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

示例 1：链接: link

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

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

代码示例如下：

2.1就地反转算法：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {ListNode first = new ListNode(0,head);ListNode l = first,r = first;while(left-- > 1){l = l.next;}while(right-- > 0){r = r.next;}ListNode next = r.next;ListNode temp = next;ListNode pre = next;ListNode cur = l.next;while(cur != next){temp = cur.next;cur.next = pre;pre = cur;cur = temp;}l.next = pre;return first.next;}
}

2.2头插法

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {ListNode first = new ListNode(0,head);ListNode pre = first;for(int i = 0; i < left - 1; i++){pre = pre.next;}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 first.next;}
}

三.反转链表中的多个区域

该类问题和第二题相似，增加的难度主要在于进行可以反转的判断，可以先求出尾结点位置来进行判断

3.1示例链接: link

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：

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

代码示例

3.2头插法

class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode first = new ListNode(0,head);// 指向链表的头结点ListNode h = first,t = first; //指向反转区间的前一个结点和结尾结点ListNode next = null;ListNode cur = null;while(t != null){//求出尾结点for(int i = 0; i < k; i++){t = t.next;if(t == null){return first.next;}}//将头尾结点区域进行反转cur = h.next;for(int i = 0; i < k - 1; i++){next = cur.next;cur.next = next.next;next.next = h.next;h.next = next;}h = cur;t = cur;}return first.next;}
}

总结

本人对于数据结构熟练度不高，如果有讲得不够好的地方，请包涵
此外：链表问题一定要画图，脑海浮现会很乱的