两两交换链表中的节点

自己写

原理为两个交换，交换参数为pre和cur。
交换成功后，连接pre的前一个pre2和cur的后一个aft。

#include <iostream>
#include <vector>
#include<algorithm> 

using namespace std;




struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
 

class Solution {
public:
   	ListNode* swapPairs(ListNode* head) {
        ListNode* pre, * cur, *temp ,*aft,*pre2,*head_test;
		//链表长度为0或者为1
        if (head == nullptr || head->next == nullptr)return head;

        ListNode test(0,nullptr);
        head_test = head->next;
        pre = head;
        pre2 = &test;
        cur = pre->next;
       
       //链表长度大于2以上
        while (cur)
        {
           
            aft = cur->next;
            if (pre != nullptr|| cur != nullptr)
            {
                temp = cur->next;
                cur->next = pre;
                pre->next = temp;
                pre2->next = cur;
            }
            else break;
            pre2 = pre;
            pre = aft;
            
            if (pre != nullptr)cur = pre->next;
            else break;
        }
        return head_test;
    }
};

int main()
{
    vector<int> head = { 1,2};

    ListNode* head_test = new ListNode(0);
    ListNode* test  , *cur = head_test;
    Solution  a;

    for (int i = 0; i < head.size(); i++)
    {
       
       ListNode* temp = new ListNode(head[i]);
       cur->next = temp;
       cur = cur->next;
      
    }
    cur->next = nullptr;

    cur = head_test;
    cout << "cur list" << endl;
    while (cur->next != nullptr)
    {
        cout << cur->val << ' ';
        cur = cur->next;
    }
    cout << cur->val << endl;


    test = a.swapPairs(head_test->next);

    while (test->next != nullptr)
    {
        cout << test->val << ' ';
        test = test->next;
    }
    cout << test->val << ' ';
	return 0;

}

卡尔

 class Solution {
  public:
      ListNode* swapPairs(ListNode* head) {

          ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
          dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
          ListNode* cur = dummyHead;
          while (cur->next != nullptr && cur->next->next != nullptr) {
              ListNode* tmp = cur->next; // 记录临时节点
              ListNode* tmp1 = cur->next->next->next; // 记录临时节点

              cur->next = cur->next->next;    // 步骤一
              cur->next->next = tmp;          // 步骤二
              cur->next->next->next = tmp1;   // 步骤三

              cur = cur->next->next; // cur移动两位，准备下一轮交换
          }
          return dummyHead->next;
      }
  };

二刷

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==nullptr || head->next==nullptr) return head;
        
        ListNode *result = head->next;
        ListNode *pre = new ListNode(0,head) ;
        ListNode *cur1 = head;
        ListNode *cur2 ;
        ListNode *cur_next ;
      
        while(cur1 != nullptr && cur1->next != nullptr)
        {
            cur2 = cur1->next;
            cur_next = cur2->next;
                
            pre->next = cur2;
            cur2->next = cur1;
            cur1->next = cur_next;
            
            pre = cur1;
            cur1 = cur_next;
        }
        return result;
    }
};

高刷题

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* headReal = new ListNode(0);
        headReal->next = head;
        
        ListNode* tmpPre = headReal;
        ListNode* tmp1 = tmpPre->next;
        ListNode* tmp2 = tmpPre->next->next;
        ListNode* tmpNext = tmpPre->next->next->next;

        while(tmpPre != nullptr && tmp1 != nullptr && tmp2 != nullptr  )
        {
            tmpPre->next = tmp2;
            tmp2->next = tmp1;
            tmp1->next = tmpNext;

            tmpPre = tmpPre->next->next;
            tmp1 = tmpPre->next;
            if( tmp1 == nullptr) break;
            tmp2 = tmpPre->next->next;
            if( tmp2 == nullptr) break;
            tmpNext = tmpPre->next->next->next;

        }


        return headReal->next;
    }
};