【leetcode】力扣热门算法之两两交换链表中的节点【中等难度】

题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

用例

1. 示例1

输入：head = [1,2,3,4]
输出：[2,1,4,3]

2. 示例 2

输入：head = []
输出：[]

3. 示例 3

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

示例代码

• 递归写法

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    if(!head||!head.next)return head;
    let next=head.next;
    head.next=swapPairs(next.next);
    next.next=head;
    return next;
};
1
2
3
4
5
6
7
8
9
10
11

• 非递归写法

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    if(!head||!head.next)return head;
    let pre=new ListNode(0);
    pre.next=head;
    let temp=pre;
    while(temp.next!=null && temp.next.next !=null){
        let start=temp.next;
        let end=temp.next.next;
        temp.next=end;
        start.next=end.next;
        end.next=start;
        temp=start;
    }
    return pre.next;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Tip

相对来说 更喜欢递归写法，但对于新手来说非递归写法更易理解。当然非递归写法理解清楚之后再去理解递归会更轻松些。