24. 两两交换链表中的节点
题目描述
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4] 输出:[2,1,4,3]
示例 2:
输入:head = [] 输出:[]
示例 3:
输入:head = [1] 输出:[1]
提示:
- 链表中节点的数目在范围
[0, 100]
内 0 <= Node.val <= 100
方法一:递归
我们可以通过递归的方式实现两两交换链表中的节点。
递归的终止条件是链表中没有节点,或者链表中只有一个节点,此时无法进行交换,直接返回该节点。
否则,我们递归交换链表
时间复杂度
java
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode t = swapPairs(head.next.next);
ListNode p = head.next;
p.next = head;
head.next = t;
return p;
}
}
cpp
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* t = swapPairs(head->next->next);
ListNode* p = head->next;
p->next = head;
head->next = t;
return p;
}
};
ts
function swapPairs(head: ListNode | null): ListNode | null {
if (!head || !head.next) {
return head;
}
const t = swapPairs(head.next.next);
const p = head.next;
p.next = head;
head.next = t;
return p;
}
python
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
t = self.swapPairs(head.next.next)
p = head.next
p.next = head
head.next = t
return p
方法二:迭代
我们设置一个虚拟头节点
接下来,我们遍历链表,每次需要交换
时间复杂度
java
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy;
ListNode cur = head;
while (cur != null && cur.next != null) {
ListNode t = cur.next;
cur.next = t.next;
t.next = cur;
pre.next = t;
pre = cur;
cur = cur.next;
}
return dummy.next;
}
}
cpp
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0, head);
ListNode* pre = dummy;
ListNode* cur = head;
while (cur && cur->next) {
ListNode* t = cur->next;
cur->next = t->next;
t->next = cur;
pre->next = t;
pre = cur;
cur = cur->next;
}
return dummy->next;
}
};
ts
function swapPairs(head: ListNode | null): ListNode | null {
const dummy = new ListNode(0, head);
let [pre, cur] = [dummy, head];
while (cur && cur.next) {
const t = cur.next;
cur.next = t.next;
t.next = cur;
pre.next = t;
[pre, cur] = [cur, cur.next];
}
return dummy.next;
}
python
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(next=head)
pre, cur = dummy, head
while cur and cur.next:
t = cur.next
cur.next = t.next
t.next = cur
pre.next = t
pre, cur = cur, cur.next
return dummy.next