题意理解

从前往后,将链表中的每两个节点交换位置。注意第1、2节点交换后,原来的第1个节点不用和第3个节点交换。

方法一

使用多个指针模拟交换节点位置的过程,指针p,q分别指向当前交换位置的两个节点,指针behind指向它们之前的一个节点。因为p,q交换位置后,behind->next发生了改变。

具体的交换过程如图所示: alt

具体代码如下:

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* swapLinkedPair(ListNode* head) {
        // write code here
        ListNode *p,*q, *behind;
        p = head;
        q = head;
        behind = head;
        bool first = true;
        while (p!=NULL)
        {
            if (p->next == NULL) break;
            behind = q;
            q = p;
            p = p->next;
            q->next = p->next;
            p->next = q;
            //判断是否是首次调换位置,head和behind要特殊处理
            if (first) {head = p; first = false;}
            else behind->next = p;
            p = q->next;
        }
        return head;
    }
};

时间复杂度: O(N)O(N)。每一个节点被遍历一次。
空间复杂度: O(1)O(1)。直接实现了节点的交换,没有开辟新的空间。

方法二

递归
我们把两个节点视为一组,可以看到swapLinkedPair函数的参数是调换位置前,两个节点中在前面的节点;而其返回值是调换位置后,两个节点中在前面的节点,而方法一中的behind是要指向该节点的。所以这里可以构成一个递归过程。

假设我们要交换head和head->next,我们用p指向head->next,q指向head->next->next。接下来先把p->next指向head,再把head->next指向后面两个节点(head->next->next和head->next->next->next)交换后在前面的结点,也就是swapLinkedPair(q)的返回值。

具体代码如下:

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* swapLinkedPair(ListNode* head) {
        // write code here
        ListNode *p,*q;
        if (head == NULL || head->next==NULL) return head;
        p = head->next;
        q = head->next->next;
        p->next = head;
        head->next = swapLinkedPair(q);
        return p;
    }
};

时间复杂度: O(N)O(N)。每一个节点被遍历一次。
空间复杂度: O(N)O(N)。递归栈的深度和节点个数一致。