原题地址:. - 力扣(LeetCode)
题目描述
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
输入:head = [1,2,3,4] 输出:[2,1,4,3]示例 2:
输入:head = [] 输出:[]示例 3:
输入:head = [1] 输出:[1]提示:
- 链表中节点的数目在范围
[0, 100]
内0 <= Node.val <= 100
解题思路
定义节点:我们使用一个
ListNode
类表示单链表的节点,包含节点的值和指向下一个节点的指针。边界条件:首先检查链表的头节点是否为空或只有一个节点。如果是,直接返回头节点,因为没有需要交换的节点。
创建虚拟头节点:使用一个虚拟头节点(
dummy
)来简化边界情况的处理,特别是处理链表的开头节点。循环交换节点:使用一个指针
tmp
遍历链表,直到没有更多的节点可以交换:
- 获取当前待交换的两个节点(
n1
和n2
)。- 进行节点交换,将
tmp.next
指向n2
,并调整n1
和n2
的next
指针。- 更新
tmp
指向n1
,为下一个交换做准备。返回结果:最终返回虚拟头节点的下一个节点,即新的头节点。
源码实现
class Solution {
public ListNode swapPairs(ListNode head) {
// 检查链表是否为空或只有一个节点
if (head == null || head.next == null) {
return head; // 直接返回原链表
}
// 创建一个虚拟头节点,方便操作
ListNode dummy = new ListNode(0);
dummy.next = head; // 虚拟节点指向原链表的头
ListNode tmp = dummy; // 用于遍历的指针
// 遍历链表,直到没有足够的节点进行交换
while (tmp.next != null && tmp.next.next != null) {
ListNode n1 = tmp.next; // 当前节点
ListNode n2 = tmp.next.next; // 下一个节点
// 进行节点交换
tmp.next = n2; // tmp指向n2
n1.next = n2.next; // n1指向n2的下一个节点
n2.next = n1; // n2指向n1
// 更新tmp指针,为下次交换做准备
tmp = n1;
}
// 返回新的头节点
return dummy.next;
}
}
复杂度分析
标签:tmp,next,链表,n1,LeetCode24,n2,节点 From: https://blog.csdn.net/qq_36070104/article/details/143456121
- 时间复杂度:O(n),其中n是链表的节点数。每个节点最多被访问两次,所以整体时间复杂度是线性的。
- 空间复杂度:O(1)。我们只使用了常数的额外空间,不需要额外的存储结构。因此空间复杂度为常数。