0024.Swap-Nodes-in-Pairs

两两交换链表中的节点

1. 题目

1.1. 描述

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

1.2. 示例

示例 1

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

示例 2

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

示例 3：

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

1.3. 提示

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

2. 思路

2.1. 迭代法

• 按照题意画图
• 时间复杂度为O(n)，空间复杂度为O(1)

2.2. 递归法

• 从链头遍历至链尾，交换末尾两结点，再依次往前交换
• 时间复杂度为O(n)，空间复杂度为O(n)

3. 代码

3.1. C++

3.1.1. 迭代法

class Solution {
public:
    ListNode swapPairs(ListNode head) {
        // 新链表
        ListNode ans = new ListNode(-1);
        ListNode p = ans;
      
        ListNode rev,tep;
        while(head!=NULL){
            // 尾插法
            p->next=head;
						// 待交换结点 2
            rev = head->next;
          
            if(rev!=NULL){
                // 待链接结点 3
                tep = rev->next;
                // 结点2链接至结点1
                rev->next = head;
                // 结点1链接至结点3
                head->next = tep;
                // 新链表链接结点2
                p->next = rev;
            }else{
                tep = NULL;
            }
						// 开启下一轮交换
            p = head;
            head = tep;
        }
        return ans->next;
    }
};

3.1.2. 递归法

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        // 空结点或只有一个结点时不需要交换操作
        if(head==NULL||head->next==NULL){
            return head;
        }
        // 经过上述递归终止条件的判断，head.next必然存在
        ListNode* rev = head->next;
        // 不断递归至最后一个结点或最后两个结点
        head->next = swapPairs(head->next->next);
        // 交换之后
        // rev 指向 head
        rev->next = head;
        return rev;
    }
};

3.2. Java

3.2.1. 迭代法

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode ans = new ListNode(-1);
        ListNode p = ans;
        ListNode rev,tep;
        while(head!=null){
            p.next = head;
            rev = head.next;
            if(rev!=null){
                tep = rev.next;

                rev.next = head;
                head.next=tep;
                p.next=rev;
            }else{
                tep = null;
            }
            p=head;
            head=tep;
        }
        return ans.next;
    }
}

3.2.2. 递归法

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode rev = head.next;
        head.next=swapPairs(head.next.next);
        rev.next = head;
        return rev;
    }
}