每天一道算题题: 24. 两两交换链表中的节点

309 阅读1分钟

题目

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 事例:

给定 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: 有兴趣欢迎关注我的公众号。