两两交换链表中的节点
2023-09-14 09:02:34 时间
递归解法
class Solution {
public:
ListNode* swapPairs(ListNode* head)
{
//在递归到最后两个节点的时候,返回head==NULL,相当于把倒数第二个节点next赋值为NULL
//就是把倒数第一个节点和倒数第二个节点进行交换
if (head == NULL || head->next == NULL)
{
return head;
}
//函数返回的是要交换两个节点的后面一个节点,相当于将交换后的两个节点在放入原链表中
ListNode* newlist = swapPairs(head->next->next);
//下面是进行两个节点交换的代码
ListNode* p = head->next;
//把原先后一个节点next指向它的前一个节点
p->next = head;
//前一个节点head指向的节点,接收newlsit的值
head->next = newlist;//原先p节点在head节点之后,此时head与p的位置互换了
//返回p节点,因为此时p排在head前面,原先指向head的节点,此时应该指向p
return p;
}
};
非递归解法
class Solution {
public:
ListNode* swapPairs(ListNode* head)
{
ListNode* dummyNode = new ListNode(0);
dummyNode->next= head;//虚节点(指向第一个有数据节点的头结点)
ListNode* temp = dummyNode;//用来遍历链表
while (temp->next != NULL && temp->next->next != NULL)//当还剩一个或没有节点的时候,停止交换
{
//每一次将temp后面两个节点进行交换操作
ListNode* node1 = temp->next;
ListNode* node2 = temp->next->next;
//交换
node1->next = node2->next;
node2->next = node1;
temp->next = node2;
//更新temp位置
temp = node1;
}
return dummyNode->next;
}
};
相关文章
- 找两个链表的公共节点
- Java实现 LeetCode 382 链表随机节点
- Java实现 LeetCode 328 奇偶链表
- Java实现 LeetCode 25 K个一组翻转链表
- Java实现 LeetCode 24 两两交换链表中的节点
- Java实现 LeetCode 21 合并两个有序链表
- LeetCode(24): 两两交换链表中的节点
- 24. 两两交换链表中的节点
- 删除链表的倒数n个节点
- 【LeetCode 24】两两交换链表中的节点
- leetCode 82.Remove Duplicates from Sorted List II (删除排序链表的反复II) 解题思路和方法
- 【 华为OD机试 2023】 单向链表中间节点(C++ Java JavaScript Python)
- 1721. 交换链表中的节点-仅遍历一次链表-考研满分答案
- 剑指 Offer 52. 两个链表的第一个公共节点-等长查找法
- 2.6 Brent链表查环算法
- 从尾到头打印链表
- [LeetCode] 234. 回文链表 ☆(翻转链表)
- leetcode 24. 两两交换链表中的节点 js实现
- [华为机试练习题]24.删除链表中的反复节点、剩余节点逆序输出
- 二叉树的二叉链表存储
- 【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点