Leetcode题库24. 两两交换链表中的节点

文章目录

• 思路
• 效果
• 代码

思路

virtual_head作为临时节点保存交换过的链表的尾部，使得left和right进行交换之后能够连接到原链表的尾部

效果

代码

struct ListNode* swapPairs(struct ListNode* head){
    if(head==NULL || head->next==NULL) return head;

    struct ListNode *left=head,*right=head->next;
    //第一次交换涉及头节点，特殊处理
    left->next=right->next;
    right->next=left;
    head=right;

    //指向即将交换的两节点的前一个节点
    struct ListNode *virtual_head=left;
    while(virtual_head->next!=NULL && virtual_head->next->next!=NULL){
        //下一对节点非空，移动指针到下一对节点
        left=virtual_head->next;
        right=left->next;

        //借助virtual_head交换left和right
        left->next=right->next;
        right->next=left;
        virtual_head->next=right;

        //更新virtual_head
        virtual_head=left;
    }

    return head;
}