题目
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 事例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
解题思路
迭代扫描
class ListNode {
constructor(val) {
this.val = val
this.next = null
}
}
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function(head) {
// 哨兵结点
let sentry = new ListNode(-1)
sentry.next = head
let prevNode = sentry
while(head && head.next) {
let firstNode = head
let secondNode = head.next
// 互换
prevNode.next = secondNode
firstNode.next = secondNode.next
secondNode.next = firstNode
// 指针移动
prevNode = firstNode
head = firstNode.next
}
return sentry.next
};
时间复杂度:O(N)。 空间复杂度:O(1)。
递归
class ListNode {
constructor(val) {
this.val = val
this.next = null
}
}
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function(head) {
// 递归终止条件
if (!head || !head.next) {
return head
}
// 假设是 1 => 2 => 3 => 4
let firstNode = head // 1
let secondNode = head.next // 2
firstNode.next = swapPairs(secondNode.next) // 返回上一个递归的返回值
secondNode.next = firstNode
return secondNode
};
时间复杂度:O(N)。 空间复杂度:O(N),因为使用了递归。
PS: 有兴趣欢迎关注我的公众号。