交换、反转链表中的节点

24.题目链接-来源:力扣(LeetCode)

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1:

输入:head = [1,2,3,4]
输出:[2,1,4,3]

思路:

本题是下一题「25. K 个一组翻转链表」的特例,理清本题思路有助于我们解决下一题。
此类题目有递归法和迭代法两种。递归法代码简洁,但由于递归本身需要的栈空间,空间复杂度为 O(1),且不易理解,故采用迭代法。
首先还是用一个「哑节点」dummy 插入链表头部。直观上理解,我们可以从头到尾一对一对地依次翻转每一段节点(在本题中,一段即有 2 个节点,而在下一题种,一段有 k 个节点),事实上这样做的效率也是最高的,因为无需额外的遍历。用指针 curFront 标记当前要处理的段的起始节点,用指针 preCur 抓住该节点的前驱,用指针 curNext (对于下一题是 curEnd) 标记当前节点对的末尾(第二个)节点,用指针 rest 标记末尾节点之后的节点,也就是链表的剩余部分。
于是我们的可以很清晰地得出每次循环的处理流程,preCur 应该指向 curNext,curFront 应该指向 rest,然后当前段内部 curFront 与 curNext 反转顺序即可。进行下一轮循环前,preCur 要指向下一段的前驱,即 curFront,然后其他指针依次接力更新。当更新失败时标记为 null,这样我们的中止条件就是待处理的某个节点(可以是 curFront,或者 curNext)为 null。
最后返回 dummy.next 即可。
时间复杂度:O(n)
空间复杂度:O(1)

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode preCur = dummy, curFront = dummy.next, curNext = curFront == null ? null : curFront.next;
while (curNext != null) {
ListNode rest = curNext.next;
preCur.next = curNext;
curNext.next = curFront;
curFront.next = rest;

preCur = curFront;
curFront = rest;
curNext = rest == null ? null : rest.next;
}
return dummy.next;
}
}