个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言今天继续学习链表的相关题目主要还是考察链表的基本操作是面试的基础题常考需要掌握。题目背景LeetCode24给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。示例 1输入head [1,2,3,4]输出[2,1,4,3]示例 2输入head []输出[]示例 3输入head [1]输出[1]提示链表中节点的数目在范围[0, 100]内0 Node.val 100题目答案第一种解法class Solution { public ListNode swapPairs(ListNode head) { ListNode dumyhead new ListNode(-1); // 设置一个虚拟头结点 dumyhead.next head; // 将虚拟头结点指向head这样方便后面做删除操作 ListNode cur dumyhead; ListNode temp; // 临时节点保存两个节点后面的节点 ListNode firstnode; // 临时节点保存两个节点之中的第一个节点 ListNode secondnode; // 临时节点保存两个节点之中的第二个节点 while (cur.next ! null cur.next.next ! null) { temp cur.next.next.next; firstnode cur.next; secondnode cur.next.next; cur.next secondnode; // 步骤一 secondnode.next firstnode; // 步骤二 firstnode.next temp; // 步骤三 cur firstnode; // cur移动准备下一轮交换 } return dumyhead.next; } }题目解析我们这里仍旧使用虚拟头节点的方式在做这种题目的时候我们最好要把流程图画出来不然容易搞混。如图所示我们把虚拟头节点设为cur然后分别用临时节点保存需要移动的节点我们这里保存的是第一个和第二个节点关于temp记录的cur.next.next.next实际上是为了步骤三交换位置。记录完之后我们就可以开始交换了首先cur.nextsecondnode,secondnode.nextfirstnode;之后交换后的firstnode节点的next实际上就是我们下次开始执行交换的节点的下个节点也就是我们保存的临时节点temp。因为是两两交换自然就是虚拟头节点的next.next.next,这里没什么深究的而此时的firstnode也就相当于一开始虚拟头节点的作用用于联系交换后面两个节点。然后就是关于循环条件如果链表有偶数个那么循环的终止条件就是cur.nextnull的时候如图所示执行完两次交换之后此时的cur等于被交换之后val3的那个位置如图因为是偶数节点那么他后面的节点自然就是null如果是奇数节点我们画个图理解一下那么也就是cur节点的next.next节点为null因为cur.next的节点没有节点与之交换。注意这两个条件的位置一定不能交换否则会报空指针异常cur.next.next ! null // 先执行这个 // cur.next 节点1 // cur.next.next 节点1.next null // 访问 null.next → 空指针异常注意其实我们在设置临时节点的时候只需要保存cur.next和cur.next.next.next,的值一般不需要设置第二个节点的临时节点去保存值因为我们拿虚拟节点交换的时候步骤一cur.nextcur.next.next也就是第二个节点变成了第一个节点交换了位置步骤二firstnodecur.next.next;这里如果不用firstnode去记录第一个节点那么它的值已经在步骤一的时候就被覆盖了步骤三照常第二种解法// 递归版本 class Solution { public ListNode swapPairs(ListNode head) { // base case 退出提交 if(head null || head.next null) return head; // 获取当前节点的下一个节点 ListNode next head.next; // 进行递归 ListNode newNode swapPairs(next.next); // 这里进行交换 next.next head; head.next newNode; return next; } }题目解析其实递归的本质就是代替循环的操作链表初始状态1 → 2 → 3 → 4 → null第一层调用swapPairs(1)head 1head.next 2不为 null不满足 base casenext head.next 2进入递归newNode swapPairs(3)因为next.next 3第二层调用swapPairs(3)head 3head.next 4不为 nullnext head.next 4进入递归newNode swapPairs(5)因为next.next null第三层调用swapPairs(5)head null→ 满足 base case返回null返回到第二层newNode null回到第二层swapPairs(3)next 4newNode null交换操作next.next head→4.next 3head.next newNode→3.next null此时链表局部4 → 3 → null返回next→ 返回节点 4状态第二层返回到第一层的newNode是节点 4且它带着4 → 3 → null这一段。回到第一层swapPairs(1)next 2newNode 4 → 3 → null交换操作next.next head→2.next 1head.next newNode→1.next 4注意此时1.next 4所以链表变成2 → 1 → 4 → 3 → null最终返回next 2作为新的头节点返回。完整结果2 → 1 → 4 → 3 → null✅关键点总结递归从链表尾部向前建立两两交换后的链表每次递归返回的是交换完这一对后这一段的头节点即原next节点newNode接收的是已经交换好的后续部分然后挂在head.next上补充变量作用是否移动dummyhead永远指向虚拟头结点用于最后返回❌ 不移动cur当前操作位置需要不断移动✅ 移动为什么用cur.next而不是dummyhead.next因为cur在移动dummyhead不动。当cur移动到后面时cur.next和dummyhead.next就完全不同了cur.next当前要交换的节点对的前一个节点dummyhead.next整个链表的头节点交换后会变化结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励