wordpress打开网站加速,重生做门户网站的小说,国外网站策划,网站 色调两两交换链表中的节点
给你一个链表#xff0c;两两交换其中相邻的节点#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题#xff08;即#xff0c;只能进行节点交换#xff09;。
示例1: 输入#xff1a;head [1,2,3,4] 输出#…两两交换链表中的节点
给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。
示例1: 输入head [1,2,3,4] 输出[2,1,4,3]
解题思路
这个问题可以通过递归或迭代来实现。下面提供一种迭代的方法1、使用两个指针 prev 和 current以及一个额外的指针 dummyHead 作为头节点。2、每次交换两个节点将它们的前后关系调整正确
具体步骤
1、初始化 dummyHead 为一个新的节点指向链表的头节点。2、初始化 prev 指向 dummyHead。3、初始化 current 指向链表的头节点。4、在循环中交换 current 和 current.next 两个相邻的节点同时更新 prev 和 current 的位置。5、指针移动完成后更新 prev 指向下一组相邻节点的前一个节点。6、重复步骤4和步骤5直到遍历完整个链表。
Java实现
public class SwapPairs {static class ListNode {int val;ListNode next;ListNode(int x) {val x;next null;}}public ListNode swapPairs(ListNode head) {ListNode dummyHead new ListNode(0);dummyHead.next head;ListNode prev dummyHead;while (head ! null head.next ! null) {// 保存当前两个相邻节点ListNode first head;ListNode second head.next;// 交换两个相邻节点prev.next second;first.next second.next;second.next first;// 更新 prev 和 head 的位置prev first;head first.next;}return dummyHead.next;}public static void main(String[] args) {// 构造链表 1 - 2 - 3 - 4ListNode head new ListNode(1);head.next new ListNode(2);head.next.next new ListNode(3);head.next.next.next new ListNode(4);// 调用 swapPairs 方法交换相邻节点SwapPairs solution new SwapPairs();ListNode result solution.swapPairs(head);// 打印交换后的链表while (result ! null) {System.out.print(result.val );result result.next;}}
}时间空间复杂度
时间复杂度O(n)其中 n 是链表的长度需要遍历一次链表。空间复杂度O(1)只需要使用常数级别的额外空间
