飞道的博客

蓝桥杯入门即劝退(十)反转链表

284人阅读  评论(0)

----------持续更新蓝桥杯入门系列算法实例------------

如果你也喜欢Java和算法,欢迎订阅专栏共同学习交流!

你的点赞、关注、评论、是我创作的动力!

-------希望我的文章对你有所帮助--------

前言:如果有一定链表基础,来学习本篇文章的实例将更好理解哦!

一、反转链表 I

题目描述

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

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

示例 2:

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

解题思路:1、本题的目标很明确,就是对整个链表进行反转,通过对于链表元素进行操作,而不是改变其Value!

2、本题较为容易理解的就是使用双指针法,即创建一个pre指针,且赋值为null,一个cur指针,表示指向当前元素。

3、首先,将cur指针初始化指向head头指针,其次再创建一个next节点,赋值为cur.next

4、其实这个next节点表示的是指向head指针的下一个元素!

5、再将cur.next指针指向pre,即改变了head的指针方向(抽象上)

6、再次,将cru赋值给pre,即完成了一次反转,最后再使得cur赋值给next,开始下一次反转

7、最后返回pre,即完成全部反转!

8、动图演示:

(图中pre为本题中的cur,原理其实一样)

 

代码实现


  
  1. public static ListNode reverseList (ListNode head) {
  2. ListNode pre= null;
  3. ListNode cru=head;
  4. while (cru!= null){
  5. ListNode next=cru.next;
  6. cru.next=pre;
  7. pre=cru;
  8. cru=next;
  9. }
  10. return pre;
  11. }

二、反转链表II

题目描述

给你单链表的头指针 head 和两个整数 leftright ,其中 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]

解题思路:1、本题是上一题的升级版,如果学会第一题,那么第二题则是会更加的得心应手

2、本题是对于部分的链表元素的反转,难度加大

3、需要确定反转链表的位置,即left和right

4、首先创建一个虚拟头节点,赋值为-1,因为head可能是变化的,并且指向head。

5、将头节点赋值给pre,并且开始遍历链表直到 left-1的位置,并且记录给RightNode节点

6、再次移动RightNode,到right+1 的位置,并且记录当前指针位置

7、开始切割,即将left到right这段链表的前一个next指针和后一个next指针置空!

8、再通过相同的方式,如第一题般反转链表

9、将反转的链表拼装回去,即可得到局部反转的链表,最后返回虚拟节点的下一个节点(head)

请问你学废了吗?

代码实现


  
  1. public ListNode reverseBetween (ListNode head, int left, int right) {
  2. ListNode D_Node= new ListNode(- 1); //虚拟节点
  3. D_Node.next=head;
  4. ListNode pre=D_Node;
  5. for( int i= 0;i<left- 1;i++){ //移到left前一个next指针
  6. pre=pre.next;
  7. }
  8. ListNode RigthNode=pre; //记录当前位置继续遍历
  9. for ( int i= 0;i<right-left+ 1;i++){
  10. RigthNode=RigthNode.next;
  11. }
  12. ListNode LeftNode=pre.next; //链表左端
  13. ListNode cur=RigthNode.next; //链表右端
  14. pre.next= null; //切割
  15. RigthNode.next= null;
  16. ReverseList(LeftNode); //反转
  17. pre.next=RigthNode; //拼接
  18. LeftNode.next=cur;
  19. return D_Node.next;
  20. }
  21. public static ListNode ReverseList (ListNode head1){
  22. ListNode pre= null;
  23. ListNode cru=head1;
  24. while (cru!= null){
  25. ListNode next=cru.next;
  26. cru.next=pre;
  27. pre=cru;
  28. cru=next;
  29. }
  30. return pre;
  31. }

感谢爱学习的你看到了最后,点个关注、赞支持一下吧!


转载:https://blog.csdn.net/m0_55278347/article/details/127929184
查看评论
* 以上用户言论只代表其个人观点,不代表本网站的观点或立场