24. Swap Nodes in Pairs

Leetcode link

题目简介

/**
 * @param {ListNode} head
 * @return {ListNode}
 */

题目给我们一个链表头指针 head

要求我们将链表内的元素两两交换，比如：

1->2->3->4->5 => 2->1->4->3->5

最后返回新的链表头

解题思路

这题有两个思路：递归与循环

循环的话，我们会需要用到一个 dummy head 来指向当前的 head

每次循环，我们都尝试把 dummy.next 与 dummy.next.next 交换，并更新 dummy 的指向

循环终止条件是 dummy.next 或 dummy.next.next 其中一个为空

Javascript——循环

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    const dummy = new ListNode(0, head)
    let prev = dummy

    while(prev.next && prev.next.next) {
        let first = prev.next
        let second = first.next

        first.next = second.next
        second.next = first
        prev.next = second
        prev = first
    }

    return dummy.next
};

Javascript——递归

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
    if (head === null || head.next === null) {
        return head;
    }
    let node1 = head,node2 = head.next;

    node1.next = node2.next;
    node2.next = node1;

    node1.next = swapPairs(node1.next);

    return node2;
};