详解链表反转问题

链表反转问题详解

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

---

---

前言

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

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

---

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

一、整个链表反转

整个链表反转即为链表的结点全部反转过来，比如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;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

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;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意事项：

递归的时候无法删除头节点，所以递归法适合用于没有头节点的链表的反转，这也是递归法的一个弊端;
要用新的头节点记录最后一个节点的位置，所以在找到该节点后要通过函数来返回该节点，即代码中的 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

以上部分参考链接: 链接: 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
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

二.反转部分链表结点

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

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;
    }
}
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
31
32
33
34
35
36
37
38
39
40

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;

    }
}
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
31
32
33

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

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

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;

    }
}
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
31

总结

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