C语言重构【24】两两交换链表中的节点

曾经终败给现在 2022-12-25 06:56 109阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
    
    你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
    
     
    
    示例 1：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70]

输入：head = [1,2,3,4]
    输出：[2,1,4,3]
    示例 2：
    
    输入：head = []
    输出：[]
    示例 3：
    
    输入：head = [1]
    输出：[1]
     
    
    提示：
    
    链表中节点的数目在范围 [0, 100] 内
    0 <= Node.val <= 100

#### 方案： ####

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
    class Solution
    { 
    public:
        ListNode *swapPairs(ListNode *head)
        { 
            //基本情况
            if (head == NULL || head->next == NULL)
                return head;
            ListNode *pre = NULL, *now = head, *alf = head->next, *ntu = alf->next;
    
            while (ntu != NULL && ntu->next != NULL)
            { 
                if (pre == NULL)
                    head = alf;
                else
                    pre->next = alf;
                //1->3
                now->next = ntu;
                //2->1
                alf->next = now;
    
                if (ntu == NULL || ntu->next == NULL)
                    break;
                //next turn
                pre = now;
                now = now->next;
                alf = now->next;
                ntu = alf->next;
            }
            //最后一轮儿
            if (pre == NULL)
                head = alf;
            else
                pre->next = alf;
            now->next = ntu;
            alf->next = now;
            return head;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70]: /images/20221120/c74cf7d6ab884bd3bc7cb260c55795c6.png