一、题目
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
二、示例
2.1> 示例 1：
【输入】head = [1,2,3,4]
【输出】[2,1,4,3]
2.2> 示例 2：
【输入】head = []
【输出】[]
2.3> 示例 3：
【输入】head = [1]
【输出】[1]
提示：
- 链表中节点的数目在范围
[0, 100]内 -
0<= Node.val <=100
三、解题思路
3.1> 思路1：遍历交换
根据题目描述，我们需要两两交换节点，然后将最终交换后的链表的头节点返回回来。那么第一个解题思路就是我们通过遍历链表中的节点，然后进行交换操作。为了方便起见，我们可以在原链表的头节点前面再创建一个虚拟节点Node(-1)，然后创建两个指针p1和p2，p1指向虚拟节点，p2指向原链表的头节点（即：Node(-1)的next节点），这样，我们就可以通过一下逻辑实现节点交换了，以输入head = [1,2,3,4,5]为例，即：
【步骤1】通过调用ListNode t = p2.next.next暂存
Node(3)节点；
【步骤2】通过调用p1.next = p2.next来将Node(-1)链接到Node(2)节点；
【步骤3】通过调用p2.next.next = p2来将Node(2)链接到Node(1)节点；
【步骤4】通过调用p2.next = t来将Node(1)链接到Node(3)节点；
【交换结果】此时链表就变为了Node(-1)——>Node(2)——>Node(1)——>Node(3)——>……了。
执行了一次两个相邻节点交换操作之后，我们需要同时移动p1和p2指针，即：
【移动p2指针】p2 = p2.next;
【移动p1指针】p1 = p1.next.next;
以上就是本题的解题思路，为了方便大家理解，我们以输入为 head = [1,2,3,4,5] 为例，来看一下具体的操作流程。请见下图所示：
3.2> 思路2：递归交换
我们除了思路一的解题方式之外，还可以通过递归的方式进行解题，其实具体思路跟思路1是极其相似的，只是写法的差异而已，此处就不再赘述和画图了，具体的解题请见下方实现2的代码部分即可。
四、代码实现
4.1> 实现1：遍历交换
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode temp = new ListNode(-1, head);
ListNode p1 = temp, p2 = head;
while(p2 != null && p2.next != null) {
ListNode t = p2.next.next;
p1.next = p2.next;
p2.next.next = p2;
p2.next = t;
p2 = p2.next;
p1 = p1.next.next;
}
return temp.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; }
* }
*/
4.2> 实现2：递归交换
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = head.next;
head.next = swapPairs(head.next.next);
newHead.next = head;
return newHead;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论