【小白爬Leetcode24】1.12 两两交换链表中的节点 Swap Nodes in Pairs

本文主要是介绍【小白爬Leetcode24】1.12 两两交换链表中的节点 Swap Nodes in Pairs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【小白爬Leetcode24】1.12 两两交换链表中的节点 Swap Nodes in Pairs

题目
- Description
- 中文描述
思路一迭代法（略显折腾）
思路二递归法
- 感谢评论区的mata川总结的递归思想

Leetcode 24

\color{#FF7D00}{medium}

点击进入原题链接：LeetCode中国站

题目

Description

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

中文描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例：

给定 1->2->3->4, 你应该返回 2->1->4->3.

思路一迭代法（略显折腾）

思路就是每两个节点进行一次角环，如果遇到剩下0个或1个节点，直接退出循环。

每次循环（以dummyhead为例）：
在这里插入图片描述
完整代码如下：

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode dummyHead(0);dummyHead.next = head;head = &dummyHead;while(head->next){if(head->next->next){ListNode* ptr = head->next->next->next;head->next->next->next = head->next;head->next = head->next->next;head = head->next->next;head->next = ptr;}else{break;}}return dummyHead.next;}
};

结果非常的好看哈哈：
在这里插入图片描述

思路二递归法

感谢评论区的mata川总结的递归思想

在这里插入图片描述
受到mata川（爪巴）的启发，写出了递归解法：

他的博客，讲递归的思想，写的非常通俗易懂，图文并茂

直接引用他的话：

“我自己在刚开始解决递归问题的时候，总是会去纠结
这一层函数做了什么，它调用自身后的下一层函数又做了什么…
然后就会觉得实现一个递归解法十分复杂，根本就无从下手。”

他总结了递归三部曲：

找整个递归的终止条件：递归应该在什么时候结束？
找返回值：应该给上一级返回什么信息？
本级递归应该做什么：在这一级递归中，应该完成什么任务？

按照他的思想，我写出了下面这段代码：

class Solution {
public:ListNode* swapPairs(ListNode* head) {if(head==NULL||head->next==NULL){return head;}ListNode* next = head->next->next;ListNode* new_head = head->next; head->next->next = head;head->next = swapPairs(next);return new_head;}
};

后来对比了他的，发现可以更简洁一些：

class Solution {
public:ListNode* swapPairs(ListNode* head) {if(head==NULL||head->next==NULL){return head;}ListNode* next = head->next;head->next = swapPairs(next->next);next->next = head;return next;}
};