为什么不自己做购物网站,下载织梦做网站软件,物业管理系统英文,张家界网站建设公司Problem: 24. 两两交换链表中的节点 题目#xff1a;给你一个链表#xff0c;两两交换其中相邻的节点#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题#xff08;即#xff0c;只能进行节点交换#xff09;。 文章目录整体思路完整代码… Problem: 24. 两两交换链表中的节点 题目给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。 文章目录整体思路完整代码时空复杂度时间复杂度O(N)空间复杂度O(1)整体思路
这段代码旨在解决一个经典的链表操作问题两两交换链表中的节点 (Swap Nodes in Pairs)。问题要求将链表中每两个相邻的节点进行交换并返回交换后的链表。例如1-2-3-4 应变为 2-1-4-3。
该算法采用了一种 迭代 的方法通过精心设计的指针操作来完成节点的交换。为了简化边界情况特别是头节点的交换它也巧妙地运用了 哨兵节点 (Sentinel Node)。
其核心逻辑步骤如下 初始化 哨兵节点创建一个 dummy 节点其 next 指向原始链表的头节点 head。这使得对第一对节点的交换与其他节点的交换逻辑完全统一。指针设置 left 指针初始化为 dummy。这个指针将始终指向待交换的一对节点的前一个节点。它的作用是连接上一组交换好的部分和当前正在交换的部分。right 指针初始化为 head。这个指针将始终指向待交换的一对节点中的第一个节点。 迭代交换 算法使用一个 while 循环来遍历并交换节点对。循环条件while (null ! right null ! right.next)。这个条件确保了至少还有一对完整的节点right 和 right.next可供交换。如果链表为空、只有一个节点或者只剩最后一个节点循环都不会执行。在循环内部核心交换逻辑 假设当前结构是 ... - left - right - right.next - ...。目标是变为 ... - left - right.next - right - ...。left.next right.next;首先将 left 的 next 指针指向 right 的下一个节点。这是将交换后的新“头”节点连接到前面的链表上。right.next right.next.next;接着将 right 的 next 指针指向它原来下一个节点的下一个节点即跳过中间的节点。left.next.next right;最后将原来 right.next 的 next 指针指向 right完成两个节点的交换。 指针前移 left right;完成一对交换后right 节点现在是这一对中的第二个在后面。我们需要为下一轮交换做准备所以将 left 指针移动到 right 的位置。right left.next;将 right 指针移动到下一对节点的第一个节点。 返回结果 循环结束后所有节点对都已交换完毕。dummy.next 指向了交换后链表的真正头节点将其返回。
完整代码
/*** Definition for singly-linked list.*/
class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val val; }ListNode(int val, ListNode next) { this.val val; this.next next; }
}class Solution {/*** 两两交换链表中的节点。* param head 原始链表的头节点* return 交换后链表的头节点*/public ListNode swapPairs(ListNode head) {// 创建一个哨兵节点简化头节点交换的逻辑。ListNode dummy new ListNode(0, head);// left 指针指向待交换对的前一个节点。ListNode left dummy;// right 指针指向待交换对的第一个节点。ListNode right head;// 循环条件确保至少还有一对完整的节点可以交换。while (null ! right null ! right.next) {// 核心交换逻辑可以想象为三步指针重定向// 假设原始是: left - n1 - n2 - ...// 其中 n1 是 right, n2 是 right.next// 1. left 的 next 指向 n2left.next right.next;// 2. n1 的 next 指向 n2 原来的 nextright.next right.next.next;// 3. n2 的 next 指向 n1left.next.next right;// 交换后链表变为: left - n2 - n1 - ...// 为下一轮交换做准备移动指针// left 移动到 n1 的位置left right;// right 移动到 n1 的下一个位置即下一对的第一个节点right left.next;}// 返回哨兵节点的下一个节点即新链表的头。return dummy.next;}
}时空复杂度
时间复杂度O(N)
循环次数while 循环遍历整个链表。right 指针每次前进两步逻辑上。整个链表被扫描了一次。每次操作在循环的每一次迭代中执行的都是常数次固定次数的指针赋值操作。
综合分析 算法的时间复杂度与链表的长度 N 成线性关系。因此时间复杂度为 O(N)。
空间复杂度O(1)
主要存储开销算法只创建了 dummy, left, right 等几个额外的指针变量。空间大小这些变量的数量是固定的与输入链表的长度 N 无关。
综合分析 算法没有使用任何与输入规模成比例的额外数据结构。因此其额外辅助空间复杂度为 O(1)。这是一个高效的原地算法。
