Swap Nodes in Pairs

佚名 6年前 (2019-05-06) 随笔 817人围观抢沙发百度已收录

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:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

code

#include <iostream>
using namespace std;

typedef struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
}ListNode;

class Solution
{
public:
    ListNode* swapPairs(ListNode* head)
    {
         if(head==nullptr)
             return head;

         ListNode *H=new ListNode(-1);
         H->next=head;
         ListNode *t=H;
         ListNode *fast=head->next;
         ListNode *slow=head;
         while(fast)
         {
             ListNode *h1=fast->next;
             slow->next=fast->next;
             fast->next=slow;
             t->next=fast;

             if(!h1)//已经检查到最后一个节点
                return H->next;
            fast=h1->next;
             slow=slow->next;
             t=t->next->next;
        }
        head=H->next;
        H->next=nullptr;
        delete H;
        H=nullptr;
        return head;
    }
};

int main()
{
    ListNode *head=new ListNode(1);
    ListNode *h=head,*h1=head;
    h->next=new ListNode(2);
    h=h->next;
    h->next=new ListNode(3);

    h=h->next;
    h->next=new ListNode(4);

    h=h->next;
    h->next=new ListNode(5);
    Solution s;
    ListNode *res=s.swapPairs(head);

    while(res)
    {
        cout<<res->val<<endl;
        res=res->next;
    }
    return 0;
}

recursion

class Solution
{
public:
    ListNode* swapPairs(ListNode* head)
    {
        ListNode *p1=head;
        if(p1==nullptr)
            return head;
        ListNode *p2=p1->next;
        if(p2==nullptr)
            return head;

        p1->next=swapPairs(p2->next);
        p2->next=p1;

        return p2;
    }
};