c++-c++编程基础之leetcode题解第24题两两交换链表中的节点.zip资源-CSDN下载

共1个文件

md：1个

需积分: 50 149 浏览量 2024-04-07 05:24:46 上传评论收藏 2KB ZIP 举报

在C++编程中，LeetCode是一个非常受欢迎的在线平台，用于练习和提升编程技能，特别是算法和数据结构。第24题"两两交换链表中的节点"是其中一道典型的链表操作题目，旨在考察程序员对链表的理解以及对指针操作的熟练程度。链表是一种线性数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的引用。在C++中，我们可以用结构体或类来表示链表节点。第24题的目标是将链表中的相邻节点两两交换，但保持其相对顺序不变。例如，对于链表1->2->3->4，交换后应变为1->3->2->4。以下是解题思路： 1. **定义链表节点**：我们需要创建一个表示链表节点的结构体或类，通常包括一个数据成员和一个指向下一个节点的指针。例如： ```cpp struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; ``` 2. **遍历链表**：使用两个指针`prev`和`curr`，初始化时`prev = nullptr`，`curr = head`，其中`head`是链表的头节点。在每次迭代中，`prev`会移动到`curr`的位置，而`curr`会移动到`curr->next`的位置。 3. **交换节点**：当`curr`不为`nullptr`时，进行以下操作： - 保存`curr->next`到临时变量`temp`，以防交换过程中丢失下一个节点的引用。 - 将`curr->next`设置为`prev`，即交换`curr`和`curr->next`的位置。 - 如果`prev`不为空（即不是链表头），则将`prev->next`设置为`temp`，恢复之前被交换的`prev`和`curr`的关系。 - 更新`prev`和`curr`，使`prev`指向`curr`，`curr`指向`temp`。 4. **结束条件**：当`curr`为空时，遍历结束，此时`prev`成为新的链表头，返回`prev`。下面是实现该功能的完整代码示例： ```cpp ListNode* swapPairs(ListNode* head) { ListNode dummy(0); dummy.next = head; ListNode* prev = &dummy; ListNode* curr = head; while (curr && curr->next) { ListNode* temp = curr->next; prev->next = temp; curr->next = temp->next; if (temp->next) { prev = curr; curr = temp->next; } else { break; } } return dummy.next; } ``` 这个函数接受一个链表的头节点，通过`swapPairs`方法将链表中的相邻节点两两交换，最后返回新链表的头节点。在LeetCode平台上，你可以提交这个解决方案并运行测试用例来验证其正确性。通过解决这类问题，不仅可以提升C++编程技巧，还能加深对链表操作的理解，这对任何IT从业者来说都是宝贵的实践经验。

资源推荐

资源详情

资源评论

收起资源包目录

c++_c++编程基础之leetcode题解第24题两两交换链表中的节点.zip （1个子文件）

c++_c++编程基础之leetcode题解第24题两两交换链表中的节点

README.md 3KB

# [24. Swap Nodes in Pairs (Medium)](https://leetcode.com/problems/swap-nodes-in-pairs/) Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)   Example 1: <img alt="" src="https://assets.leetcode.com/uploads/2020/10/03/swap_ex1.jpg" style="width: 422px; height: 222px;"> <pre>Input: head = [1,2,3,4] Output: [2,1,4,3] </pre> Example 2: <pre>Input: head = [] Output: [] </pre> Example 3: <pre>Input: head = [1] Output: [1] </pre>   Constraints: <ul> <li>The number of nodes in the list is in the range <code>[0, 100]</code>.</li> <li><code>0 <= Node.val <= 100</code></li> </ul> **Companies**: [Facebook](https://leetcode.com/company/facebook), [Amazon](https://leetcode.com/company/amazon), [Microsoft](https://leetcode.com/company/microsoft), [Bloomberg](https://leetcode.com/company/bloomberg) **Related Topics**: [Linked List](https://leetcode.com/tag/linked-list/), [Recursion](https://leetcode.com/tag/recursion/) **Similar Questions**: * [Reverse Nodes in k-Group (Hard)](https://leetcode.com/problems/reverse-nodes-in-k-group/) * [Swapping Nodes in a Linked List (Medium)](https://leetcode.com/problems/swapping-nodes-in-a-linked-list/) ## Solution 1. ```cpp // OJ: https://leetcode.com/problems/swap-nodes-in-pairs/ // Author: github.com/lzl124631x // Time: O(N) // Space: O(1) class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode h, *tail = &h; while (head && head->next) { auto p = head, q = head->next; head = q->next; q->next = p; tail->next = q; tail = p; } tail->next = head; return h.next; } }; ``` Or ```cpp // OJ: https://leetcode.com/problems/swap-nodes-in-pairs/ // Author: github.com/lzl124631x // Time: O(N) // Space: O(1) class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode dummy, *p = &dummy; dummy.next = head; while (p->next && p->next->next) { auto next = p->next; p->next = next->next; next->next = p->next->next; p->next->next = next; p = next; } return dummy.next; } }; ```

评论收藏

内容反馈