一、前言
每日算法坚持第二天，该专栏争取日日更新，加油
二、简介和示例
简介
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
链表数据结构
public class ListNode { public int val; public ListNode next; public ListNode() { } public ListNode(int val) { this.val = val; } public ListNode(int val, ListNode next) { this.val = val; this.next = next; } } 复制代码
示例1
网络异常，图片无法展示
|
输入： head = [1,2,3,4] 输出： [2,1,4,3] 复制代码
示例2
输入： head = [] 输出： [] 复制代码
示例3
输入： head = [1] 输出： [1] 复制代码
提示
- 链表中节点的数目在范围
[0, 100]内 0 <= Node.val <= 100
三、解题
思路分析
这个题的思路有两种， 一种是使用递归来做， 一种是使用虚拟头节点来做， 我使用的是虚拟头节点方法
首先，我们假设链表结构如图所示
网络异常，图片无法展示
|
我们需要两两交换链表中的节点，变成如图所示的结构
网络异常，图片无法展示
|
这边我们使用虚拟头节点的方式，为该链表创建一个头节点，不然的话没有指针指向第一个节点，不好去操作
网络异常，图片无法展示
|
我们要进行的操作如下：
- 将节点2放置到节点1的位置
- 节点1的 next指向后面不变的节点3地址
- 节点2的 next指向节点1
网络异常，图片无法展示
|
代码实现
方法入参是 ListNode head
首先我们新建一个虚拟节点, 并将其指向我们的链表 head， 同时返回的时候注意不要直接返回
ListNode dummyNode = new ListNode(0); dummNode.next = head; ... return dummNode.next; 复制代码
设置一个我们要对其进行修改的链表
ListNode prev = dumm 复制代码
接下来就要对我们的链表进行循环操作，去对节点进行位置交换
但是这里有一个地方需要注意，那就是循环的中止条件，如下图所示，进行第三次循环的时候链表只剩下一位，不能够进行两两交换了，那肯定要中止循环了，这个时候的判断条件是 链表.next.next ！= null， 但是这是基于我们的链表节点是单数的情况下， 如果是偶数的情况下， 我们循环的终止条件应该是 链表.next != null， 而且这两个条件的执行顺序也要注意，应该是 链表.next != null 在前，因为 链表为null 的情况下 链表.next.next会报空指针异常
网络异常，图片无法展示
|
具体代码如下：
while(prev.next !=null && prev.next.next != null){ } 复制代码
在循环内具体的操作：
- 缓存后面不变的节点3
- 缓存1节点
- prev.next更改为2节点
- 1节点.next = 3节点
- 2节点.next = 1节点
- 将prev跟改为还未交换位置的节点
- 具体代码如下所示
// 缓存不变的链表信息（只动两个节点进行位置交换， 将两个节点之后的节点缓存下来） ListNode temp = prev.next.next.next; // 缓存第一个节点信息（先将第二个节点的位置放到第一个节点的位置上， 第一个节点就没有了节点信息） ListNode temp1 = prev.next; // 将第二个节点提取到第一个节点的位置 prev.next = prev.next.next; // 将不变的链表放置到 原第一个节点后面 temp1.next = temp; // 将原第一个节点放置到现第二个节点的位置 prev.next.next = temp1; // 链表移动两位 prev = prev.next.next; 复制代码
四、代码展示
public static ListNode swapPairs(ListNode head) { // 设置虚拟头节点 ListNode dummyNode = new ListNode(0); dummyNode.next = head; ListNode prev = dummyNode; // 先进行下一个节点的判断， 在进行下下个节点的判断， 避免空指针异常 while (prev.next != null && prev.next.next != null) { // 缓存不变的链表信息（只动两个节点进行位置交换， 将两个节点之后的节点缓存下来） ListNode temp = prev.next.next.next; // 缓存第一个节点信息（先将第二个节点的位置放到第一个节点的位置上， 第一个节点就没有了节点信息） ListNode temp1 = prev.next; // 将第二个节点提取到第一个节点的位置 prev.next = prev.next.next; // 将不变的链表放置到 原第一个节点后面 temp1.next = temp; // 将原第一个节点放置到现第二个节点的位置 prev.next.next = temp1; // 链表移动两位 prev = prev.next.next; } return dummyNode.next; } 复制代码
五、提交代码
网络异常，图片无法展示
|
