题解 | #两两交换链表的节点#

两两交换链表的节点

http://www.nowcoder.com/practice/71f95c23810349f782a1aa6c9bd714b4

两两交换链表的节点

题意

给一个链表，两个两个的实际的交换节点

方法

每两个一处理

分析

既然是两两交换，那么当我们把前两个处理完以后，后面剩余的部分可以递归用同样的方法处理

所以每次把第二个作为新的根，指向第一个节点

而第一个节点指向递归后面的节点

代码

/**
 * 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) {
        if(head == NULL)return NULL; // 本身是空
        if(head->next == NULL) return head; // 奇数个
		// head r r1 => r head r1
        ListNode* r = head->next; // 新的根
        ListNode* r1 = head->next->next; // 三个往后
        r->next = head; // 指向第一个
        head->next = swapLinkedPair(r1); // 第一个指向递归
        return r;
    }
};

复杂度分析

空间复杂度: 主要和递归深度相关，空间复杂度为 $O (n)$

时间复杂度: 对于每两个节点，操作代价为常数，所以总时间复杂度为 $O (n)$

转换成数组再处理

分析

先把链表转换成数组

再两两一对改造指向每个

对于每两个一组，后一个直接指向前一个，而前一个应该指向下一组的起始，根据下一组个数是0,1,2处理各不相同

最后输出链，也需要注意根据节点是1个还是大于1个起始点有不同

样例

以样例数据为例

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) {
        if(head == NULL)return NULL;
        vector<ListNode*> nodes; // 转化成数组
        ListNode* p = head;
        while(p){
            nodes.push_back(p);
            p = p->next;
        }
        for(int i = 0;i < nodes.size();i++){
            if(i%2 == 0){ // 两个一组的前一个
                if(i + 3 < nodes.size()){ // 后面有不少于2个点
                    nodes[i]-> next = nodes[i+3];
                }else if(i + 2 < nodes.size()){ // 后面仅有一个点
                    nodes[i]-> next = nodes[i+2];
                }else{ // 这就是结尾
                    nodes[i]-> next = NULL;
                }
            }else{ // 两个一组的后一个
                nodes[i] -> next = nodes[i-1];
            }
        }
        return nodes.size() > 1 ? nodes[1]:nodes[0]; // 起始节点不同
    }
};