[力扣_24] 两两交换链表中的节点

题目入口：点击进入

相关算法：

• 双指针——时间复杂度O(n)，空间复杂度O(1)

思路和算法：

由于是一道中等题，迭代和递归的解法相对来说复杂，如若感兴趣可以观看题解中各路大神的解法，我采用的思路是利用多指针实现迭代来交换

迭代解法

迭代实现 迭代实现需要很小心的处理节点的指向。

• 设置虚拟头结点 dummy，因为真实头结点有可能要换，设置了 dummy 后，能对各种情况统一处理，dummy.next 就能找到头结点。
• 开启 while 循环，一对结点的交换有三个指针要改变，见下图。
• 指针推进，准备交换下一对结点。
• 最后返回 dummy.next 。

struct ListNode* swapPairs(struct ListNode* head){

     if(!head) return NULL;//特判

     struct ListNode *di=(struct ListNode*)malloc(sizeof(struct ListNode));//虚结点
     di->next=head;
     struct ListNode *p,*s,*pre;

     pre=di;
     p=head;
     s=head->next;

     while(p&&s)
     {
         pre->next=s;
         p->next=s->next;
         s->next=p;

         pre=p;
         p=pre->next;
         if(p) s=p->next;
     }
     return di->next;
}

本文链接：