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

题目入口:点击进入

相关算法:

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

思路和算法:

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

迭代解法

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

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

img

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;
}

本文链接:

https://nullcode.fun/71.html
1 + 1 =
快来做第一个评论的人吧~