【算法专题--链表】两两交换链表中的节点 -- 高频面试题（图文详解，小白一看就懂！！！）

目录

一、前言

二、题目描述 

三、解题方法

⭐双指针 -- 采用哨兵位头节点

🥝 什么是哨兵位头节点？

🍍 解题思路   

🍍 案例图解  

四、总结与提炼 

五、共勉  

---

一、前言

        两两交换链表中的节点 这道题，可以说是--链表专题--，最经典的一道题，也是在面试中频率最高的一道题目，通常在面试中，面试官可能会从多个方面考察这道题目，所以大家需要对这道题目非常熟悉哦！！
       本片博客就来详细的讲讲解一下 两两交换链表中的节点 的实现方法，让我们的面试变的更加顺利！！！ 

二、题目描述 

题目链接：24. 两两交换链表中的节点 - 力扣（LeetCode）

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。 

三、解题方法

⭐双指针 -- 采用哨兵位头节点

🥝 什么是哨兵位头节点？

首先，先来了解一下什么是  哨兵位---头节点 ？   

• 它是一个附加的链表结点，该 结点 作为 第一个节点，它的数据域不存储任何东西，只是为了操作的方便而引入的。
• 也就是说，如果一个链表有哨兵节点的话，那么链表表的第一个元素应该是链表的第二个节点。

   哨兵位 --- 头节点的作用：  

• 比如向链表中插入一个节点，对于没有哨兵位的单链表，当待插入的节点为链表的第一个节点，由于没有前驱，需要进行特殊处理，从而代码的复杂性增加。 
• 如果有哨兵位头节点，则第一个节点的处理方式与其它节点相同，可以统一进行处理。

---

 🍍 解题思路   

• 我们设置一个哨兵头节点 pre_head，初始时指向 pre_head ->head ，然后设置两个指针 pre 和 cur，初始时 pre 指向 pre_head，而 cur 指向 head。

• 接下来，我们遍历链表，每次需要交换 pre 后面的两个节点，因此我们先判断 cur 和 cur.next 是否为空，若不为空，则进行交换，否则终止循环。

---

🍍 案例图解  

  链表：【1，2，3，4】 

• 创建 哨兵位头节点 和 双指针，开始遍历整个链表 

•  开始 交换 节点 1、2 ，先把 1 指向 3

• 再把 2 指向 1，进行交换

•  再把 -1 指向 2，进行交换

•  完成 第一次交换，双指针，向前移动，准备进行下一次交换

•  重复，上述操作，进行 节点3、4 交换

• 当 cur ==nullptr 时 循环结束 ，返回 pre_head->next 

---

复杂度分析 ： 

• 时间复杂度：O(n)     其中 n为链表长度。
• 空间复杂度：O(1)    仅用到若干额外变量。

---

代码：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        // 创建一个哨兵位 头节点，并连接 原来的头节点
        ListNode* pre_head = new ListNode(-1,head);
        // 三指针 解法
        ListNode* pre = pre_head;
        ListNode* cur = head;
 
        //  cur != nullptr 表示偶数个节点  ， cur->next!=nullptr 表示奇数个节点
        while(cur!=nullptr && cur->next!=nullptr)
        {
            ListNode* nextnode = cur->next;
 
            // 开始翻转
            cur->next = nextnode->next;
            nextnode->next = cur;
            pre->next = nextnode;
            // 指针向后移动，准备下一次翻转
            pre = cur;
            cur = cur->next;
        }
        return pre_head->next;
 
    }
};

 四、总结与提炼 

       最后我们来总结一下本文所介绍的内容，本文讲解来一道力扣中有关 两两交换链表中的节点的题目，这道题目是校招笔试面试中有关链表章节非常高频的一道题目，大家下去一定要自己再画画图，分析一下，把这段代码逻辑自己实现一遍，才能更好地掌握  

五、共勉  

       以下就是我对 两两交换链表中的节点 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 链表专题 的理解，请持续关注我哦！！！