当前位置：首页 > news >正文

LeetCode[中等] 24.两两交换链表中的结点

news 2025/7/4 23:02:30

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

思路：递归

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

对 newHead.next 调用递归，将除了前两个结点以外的部分完成交换；
head.next 指向递归调用之后的头结点；
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 层。

思路：迭代

需要在头结点head之前新建一个哑结点dummyHead，为了交换 node1 和 node2，需要依次进行以下操作：

将 temp.next 指向 node2；
将 node1.next 指向 node2.next；
将 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;}
}