题目描述
24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
1
2
| 输入：head = [1,2,3,4]
输出：[2,1,4,3]
|
示例 2：
示例 3：
提示：
- 链表中节点的数目在范围
[0, 100] 内
0 <= Node.val <= 100
解题思路
递归
迭代
代码实现
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public class Solution24Case1 {
public static ListNode swapPairs(ListNode head) {
if (null == head || null == head.next) {
return head;
}
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}
public static void main(String[] args) {
ListNode node5 = new ListNode(5);
ListNode node4 = new ListNode(4, node5);
ListNode node3 = new ListNode(3, node4);
ListNode node2 = new ListNode(2, node3);
ListNode node1 = new ListNode(1, node2);
ListNode listNode = swapPairs(node1);
System.err.println(listNode);
}
}
|
迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public class Solution24Case2 {
public static ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = 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;
}
public static void main(String[] args) {
ListNode node5 = new ListNode(5);
ListNode node4 = new ListNode(4, node5);
ListNode node3 = new ListNode(3, node4);
ListNode node2 = new ListNode(2, node3);
ListNode node1 = new ListNode(1, node2);
ListNode listNode = swapPairs(node1);
System.err.println(listNode);
}
}
|