赞
踩
链表反转类问题是链表问题中比较典型的问题,具有一定的难度,本文将会进行详细讲解
提示:这里可以添加本文要记录的大概内容:
链表是数据结构中的一种线性数据结构,它的结构可以理解为一个结构体,内部存储着一个值和其对下一个链表的指向。
链表的种类很多,主要有单链表(本文所有题目都是讲解单链表),双链表,循环链表,他们的结构大同小异,都是类似的结构体指向,只是单链表只有一个指针,双链表存在两个 两个指针,循环链表的尾结点指向不同
提示:以下是本篇文章正文内容,下面案例可供参考
整个链表反转即为链表的结点全部反转过来,比如1->2->3->4,变成4->3->2->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; } }
使用栈来进行存储的话往往是只进行数据交换
头插,意思就是把结点依次放到头节点的下一个位置,当每个结点都一一放到头结点后面就可以实现反转
代码如下(示例):
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;
}
}
图片:
代码如下(示例):
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)
三指针:
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; }
给你单链表的头节点 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.将反转后的区间进行拼接
注意事项:往往在头结点前插入一个虚拟头结点,防止区间进行反转影响指向
给你单链表的头指针 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]
/** * 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; } }
/** * 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; } }
该类问题和第二题相似,增加的难度主要在于进行可以反转的判断,可以先求出尾结点位置来进行判断
给你链表的头节点 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]
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; } }
本人对于数据结构熟练度不高,如果有讲得不够好的地方,请包涵
此外:链表问题一定要画图,脑海浮现会很乱的
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。