题目描述

Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given1->2->3->4, you should return the list as2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

题目大意

给定一个链表，交换每两个相邻的链表结点。
不能修改结点值，只改变链表指向。

思路

首先是递归思路，在递归过程中，判断结点的情况，共有三种情况：
（1）当前结点为NULL，或者当前结点是落单的结点；
（2）正好剩下最后一对结点；
（3）还剩至少三个以上的结点。
针对第一种情况，直接返回该结点给上一层递归调用的地方；
针对第二种情况，就直接交换指向，然后把当前的第一个结点返回；
针对第三种情况，交换结点指向，并且，递归判断下面的结点。

代码

#include<iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

typedef ListNode* node;

ListNode *swapPairs(ListNode *head)
{
    // 当前结点是NULL
    // 或者当前结点落单了，没有与之成对的结点
    if(head==NULL || head->next==NULL)
    {
        return head;
    }
    // 当前的结点是最后一对结点，再往下是NULL
    else if(head->next->next == NULL)
    {
        node tmp_node = head->next;
        tmp_node->next = head;
        head->next = NULL; // 把原先的第一个结点的指向置为NULL
        return tmp_node; // 返回当前的第一个结点
    }
    // 还有至少三个及以上的结点
    else
    {
        node tmp_node = head->next;
        node new_node = tmp_node->next;
        tmp_node->next = head;
        head->next = swapPairs(new_node); // 继续向后递归
        return tmp_node;
    }
}

int main()
{

    return 0;
}

以上。