24. Swap Nodes in Pairs

problem description

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

algorithm thought

第三次做题真的就很有经验了，看到链表题并且返回的是一个链表直接递归解决。这题不递归肯定也能做，也不是很难，但是递归能省好多事

code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return head;
        ListNode*tmp=head->next;
        head->next=swapPairs(tmp->next);
        tmp->next=head;
        return tmp;
    }
};

algorithm analysis

很简单的题，时间复杂度O(n)