24亮亮交换链表中的节点

24. 两两交换链表中的节点

下面是题目

下面是给出的代码模板

/**
 * 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) {
 
    }
};

我们用两种方法来解决这道题目

第一种，迭代法

/**
 * 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) {
        //这里，我们新建一个列表，来存储改变后的链表
        ListNode* p = new ListNode(0);
        //p是有0节点的，p->next 是 head的头节点
        p->next = head;
        // 再新建一个节点，让他等于p的头节点
        ListNode*cur = p;
        //下面开始迭代
        while(head!=NULL && head->next!=NULL)
        {
            //建立两个节点，分别是左节点和右节点。
            ListNode *leftNode = head;
            ListNode*rightNode = head->next;
            //在交换之前，我们要考虑一个问题，怎么让p保存每个节点的值？
            //所以，我们先用cur节点指向右节点，当节点交换后，cur节点指向的就是新链表的第一个节点了
            cur->next = rightNode ;
            //进行交换
            leftNode->next = rightNode->next;
            rightNode->next = leftNode;
            //把cur想象成一个迭代器，然后每次在执行完p链表中更新两个节点
            //现在，完成任务后，把cur指向最后一个节点
            cur = leftNode;
            //最后，把head指向更新完后的节点的下一节点
            head = leftNode->next;    
        }
        return p->next;
    }
};

第二种，递归法

/**
 * 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) {
        //判断head和head->next 是否为空
        if(head == NULL||head->next==NULL)
        return head;
         
         //新建p节点，让p指向第二个节点 
           ListNode*p = head->next;
        //然后，需要截取p后的链表
           ListNode *temp = p->next;
        //进行两个节点的交换
           p->next =head;
        //然后，head要指向交换完后的temp链表
           head->next = swapPairs(temp);
            return p;
    }
};