题目
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
分析
递归：
不需要注重过程，只需要结果。结果就是每相邻的两个节点交换位置，那么递归处就是将后一个节点变成该两个相邻直接的头节点，然后将指针交换
迭代：
使用哑节点； 定义cur（当前指针）；相邻的l（左指针）r（右指针）
/**
* 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; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
// 解法一：迭代
return swap01(head);
// 解法二：递归
// return swap02(head);
}
// 解法一：使用多指针迭代的方式
// 参考视频：https://www.bilibili.com/video/BV1GY411b7mP?spm_id_from=333.337.search-card.all.click&vd_source=3f506dfd7b2a19c74f99363591d70f4c
private static ListNode swap01(ListNode head){
if(head==null||head.next==null){
return head;
}
ListNode p=new ListNode();
p.next=head;
ListNode cur=p;
while(cur.next!=null&&cur.next.next!=null){
ListNode l=cur.next;
ListNode r=cur.next.next;
cur.next=r;
l.next=r.next;
r.next=l;
cur=l;
}
return p.next;
}
// 解法二：使用递归的方法
// https://lyl0724.github.io/2020/01/25/1/
private static ListNode swap02(ListNode head){
// base case
if(head==null || head.next==null){
return head;
}
// 记录相邻节点
ListNode next=head.next;
// 重头节点后移两个节点
head.next=swap02(next.next);
// 开始递归,交换指针
next.next=head;
return next;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96236.html
