[力扣_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;
}