链表-24.两两交换链表中的结点-力扣(LeetCode)

白天的黑夜

发布于 2025-10-22 17:17:29

6360

文章被收录于专栏：leetcode题目解析和知识分享leetcode题目解析和知识分享

一、题目解析

1、不能修改节点内部值

2、节点个数为[0，100]

二、算法原理

解法：循环(模拟)

1、结点个数特殊处理

当结点个数为0or1时，直接返回head即可

2、定义4个指针

tail、cur1、cur2和nnext，用于交换和链接前后节点

3、循环条件

观察到只有cur1和cur2都不为nullptr时，循环才会继续

4、cur1和cur2特殊情况判断

1、cur1为nullptr时，可以跳出循环直接返回结果，即只有两个结点交换

2、cur1不为nullptr时，更新cur2=cur1->next

3、cur2为nullptr时，nnext不更新

4、cur2不为nullptr时，更新nnext=cur2->next

5、返回结果

我们定义了哨兵位结点newhead，直接返回newhead->next

三、代码示例

class Solution {
public:
    ListNode* swapPairs(ListNode* head)
    {
        if(head == nullptr || head->next == nullptr) return head;//0or1个节点
        ListNode* newhead = new ListNode();
        ListNode* tail = newhead;
        ListNode* cur1 = head;
        ListNode* cur2 = head->next;
        ListNode* nnext = cur2->next;
        while(cur1!=nullptr && cur2!=nullptr)
        {
            tail->next = cur2;
            cur2->next = cur1;
            cur1->next = nnext;
            tail = cur1;
            cur1=cur1->next;
            if(cur1 == nullptr) break;
            else cur2 = cur1->next;
            if(cur2 != nullptr) 
                nnext = cur2->next;
        }
        return newhead->next;    
    }
};