“将给定链表中相邻的节点交换,返回交换后的链表。”
题目链接:
来源:力扣(LeetCode)
链接:24. 两两交换链表中的节点 - 力扣(LeetCode) (leetcode-cn.com)
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
输入: head = [1,2,3,4]
输出: [2,1,4,3]
示例 2:
输入: head = [1]
输出: [1]
这个题可以采用递归的方式实现链表中相邻节点的交换。
递归的终止条件是链表中没有节点,或者链表中只有一个节点,这个时候无法进行交换。
那么接下来就是交换了,比如,链表中有两个节点,在交换节点后,原链表的头结点就变成新链表的第二个节点,原链表的第二个节点变成新链表的头结点。
其余节点递归地实现,递归地两两交换后,更新节点之间的指针关系,即可完成整个链表的交换。
代码参考:
public class Solution {
public ListNode SwapPairs(ListNode head) {
//递归结束判断
if (head?.next == null)
return head;
//替换
var val = head.next.val;
head.next.val = head.val;
head.val = val;
//递归
SwapPairs(head.next.next);
return head;
}
}
时间复杂度 : O(n)
其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作。
空间复杂度: O(n)
其中 n 是链表的节点数量。空间复杂度主要取决于递归调用的栈空间。
继续引用那句话,递归就像学霸学习,看似什么都没做,其实都做完了。