题目:给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)
示例 1:
解题思路
对于这道题我们可以为原链表增加一个哨兵卫,然后创建三个指针,最前面的指针用于判断是否还存在需要交换的节点,后面的两个节点用于交换两个节点。
图解:
下面创建三个指针,pre,node1,node2。
第一步:我们运用指针让node1指向的节点的next变为node2指向节点的next(这一步是为了链接好整个链表)
第二步:我们让node2的next指向node1
此时的链表图就变成了:
下面我们再让pre直接赋值为node1,开始下面两个节点的交换。
既然我们要让原链表的所有元素最后都会两两交换,那肯定是要使用循环的但是循环的条件要怎么去判断呢?我们要使用哪一个指针作为循环的判断条件呢?这里我们就使用pre指针当pre指针的next和pre指针next的next都还存在值而不是NULL那,证明原链表的后面还有至少两个元素这两个元素是可以交换的。
下面是c代码的实现:
struct ListNode* swapPairs(struct ListNode* head)
{
//方法使用三指针迭代,我们额外将一个哨兵卫将其链接给给予我们的链表
//然后我们只用改变这个哨兵卫的后两个指针指向即可,最后再将指向哨兵卫的这个指针指向下一个相当于哨兵卫节点功能的节点
struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
tmp->next = head;
struct ListNode* newhead = tmp;
while (tmp->next && tmp->next->next)//当tmp的后面两个节点都不为空时表示我已交换下面的两个节点
{
struct ListNode* node1 = tmp->next;
struct ListNode* node2 = node1->next;
tmp->next = node2;
node1->next = node2->next;
node2->next = node1;
tmp = node1;
}
return newhead->next;//这里的newhead指向的我们创建的那个哨兵卫,哨兵卫的next才是指向交换元素后链表的第一个节点
}//最简单的方法时间复杂度o(n)空间复杂度o(1)