长沙seo外包服务_中信建设有限责任公司企查查_网络舆情监测平台_亚洲7号卫星电视

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

 思路：递归

头结点head，第二个结点head.next, 交换结点之后，原第二个结点变成新链表的头结点，令newHead = head.next。递归思路为：

1. 对 newHead.next 调用递归，将除了前两个结点以外的部分完成交换；
2. head.next 指向递归调用之后的头结点；
3. newHead.next 指向head。

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int val=0, ListNode next=null) {*         this.val = val;*         this.next = next;*     }* }*/
public class Solution {public ListNode SwapPairs(ListNode head) {if(head == null || head.next == null)return head;ListNode newHead = head.next;head.next = SwapPairs(newHead.next);newHead.next = head;return newHead;}
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个结点进行更新指针的操作，每个结点的更新指针操作的时间都是 O(1)。

• 空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用栈的深度，递归调用栈最多不会超过 n 层。

思路：迭代

为了交换 node1​ 和 node2​，需要依次进行以下操作：

1. 将 temp.next 指向 node2​；

2. 将 node1​.next 指向 node2​.next；

3. 将 node2​.next 指向 node1​。

public class Solution {public ListNode SwapPairs(ListNode head) {ListNode dummyHead = new ListNode(0, head);ListNode temp = dummyHead;while (temp.next != null && temp.next.next != null) {ListNode node1 = temp.next;ListNode node2 = temp.next.next;temp.next = node2;node1.next = node2.next;node2.next = node1;temp = node1;}return dummyHead.next;}
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表中的每个结点一次，每个结点的反转操作的时间都是 O(1)。

• 空间复杂度：O(1)。