- 题目链接
- 源代码 github 地址
- 1、题目要求
- 2、思路分析 - 单指针以及两个临时指针
- 2.1 整个流程图示 参考 代码随想录
- 3、执行代码 - Java
- 4、问题反思
- 5、小结
源代码 github 地址https://leetcode-cn.com/problems/swap-nodes-in-pairs/
1、题目要求https://github.com/YIMEng-0/DataStructure
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表;
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换;
使用虚拟头结点的思路进行解决;
1、脑海中出现一个带有虚拟头结点的链表;
2、让虚拟头结点的 next 指向链表的 next;
3、创建需要使用的指针 cur 指向虚拟头结点;
4、创建两个临时的结点用来保存,temp = cur.next 以及 temp1 = cur.next.next.next;
当 cur.next != null 以及 cur.next.next != null 的时候执行下面的代码
5、cur.next = cur.next.next;
6、cur.next.next = temp;
7、cur.next.next.next = temp1;
8、cur = cur.next.next
完成了链表的交换 *** 作,退出来循环;
9、返回虚拟头结点的 next
2.1 整个流程图示 参考 代码随想录https://programmercarl.com/0024.两两交换链表中的节点.html#_24-两两交换链表中的节点
package com.luobin.力扣题目.力扣_链表.力扣024两两交换链表中的节点; public class Solution { public ListNode swapPairs(ListNode head) { // 设置虚拟头结点 ListNode dummmyHead = new ListNode(0); ListNode cur = dummmyHead; dummmyHead.next = head; while(cur.next != null && cur.next.next != null) { ListNode temp = cur.next; ListNode temp1 = cur.next.next.next; temp = cur.next; temp1 = cur.next.next.next; // 进行第一步的链接,第一个元素,链接到第三个元素 cur.next = cur.next.next; // 第二步链接 cur.next.next = temp; // 第三步的连接 cur.next.next.next = temp1; cur = cur.next.next; } return dummmyHead.next; } }4、问题反思
1、为什么使用虚拟头结点?
这样子可以不用单独的考虑头结点与其他结点的不同之处,可以做到统一处理;
2、关于 cur.next 的理解
cur.next 保存了下一个结点的地址,但是这个地址保存在自己的结点上面的;
上面的代码有的结点使用了 三次 next ,其实是虚拟结点的next ,真实第一个结点的 next ,真实第二个结点的 next; 不是真实第三个结点;小心这个地方容易晕针,因为指针有点多;
4、关于程序中指针地址的更新问题;
在第一步的时候,cur.next = cur.next.next;
下面第二部 *** 作的时候,cur.next.next,是图中 结点2 的 next 不是 结点 1 的 next
4、关于返回值
返回的是调整好的链表的头结点,是不需要虚拟头结点的,否则在力扣题目中是无法通过的;一般在力扣中的是返回链表的头结点;
这个题目使用了一个指针加上两个临时指针的形式,通过对于链表的 *** 作,实现了相邻的两个元素实现了交换,除此之外,这个题目可以使用递归的方式进行求解;
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)