leetcode刷题（36）——24.两交换链表中的节点
leetcode刷题（36）——24.两交换链表中的节点
老马的编程之旅
发布于 2022-06-22 13:33:03
发布于 2022-06-22 13:33:03
文章被收录于专栏：深入理解Android
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3
题解： 这个题目有2种解法，一个是比较容易想到的循环求解，另外一个是比较难想到的递归求解
解法1:循环求解 关键点在于设置一个pre节点指向链表的头节点，很多链表题目的技巧都是这样设置一个pre，届时交换完毕后，直接返回pre.next即可。还需要一个temp存放目前循环到的节点，还有终止循环的条件， 因为需要2个进行交换，所以条件自然是temp.next!=null&&temp.next.next!=null。
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode pre = new ListNode(0);
pre.next = head;
ListNode temp = pre;
while(temp.next!=null&&temp.next.next!=null){
ListNode start = temp.next;
ListNode end = temp.next.next;
temp.next = end;
start.next = end.next;
end.next = start;
temp = start;
}
return pre.next;
}
}解法2:递归 递归写法要观察本级递归的解决过程，形成抽象模型，因为递归本质就是不断重复相同的事情。而不是去思考完整的调用栈，一级又一级，无从下手。如图所示，我们应该关注一级调用小单元的情况，也就是单个f(x)。
其中我们应该关心的主要有三点：
返回值 调用单元做了什么 终止条件 在本题中：
返回值：交换完成的子链表 调用单元：设需要交换的两个点为 head 和 next，head 连接后面交换完成的子链表，next 连接 head，完成交换 终止条件：head 为空指针或者 next 为空指针，也就是当前无节点或者只有一个节点，无法进行交换
递归解法
class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-01-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
