day3
两两交换链表中的节点
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。 - 递归
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50public class Solution {
public ListNode swapPairs(ListNode head) {
// 如果链表为空或者只有一个节点,无需交换
if (head == null || head.next == null) {
return head;
}
ListNode one = head;
ListNode two = one.next;
ListNode three = two.next;
// 交换节点
two.next = one;
one.next = swapPairs(three);
return two;
}
}
* 迭代
```java
<p1>很奇妙的一种写法,给每一个节点都抽象化成数字</p1>
```java
public class Solution {
public ListNode swapPairs(ListNode head) {
// 如果链表为空或者只有一个节点,无需交换
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
while (pre.next != null && pre.next.next != null) {
ListNode one = pre.next;
ListNode two = one.next;
ListNode three = two.next;
// 交换节点
one.next = three;
two.next = one;
pre.next = two;
// 更新 pre 指针
pre = one;
}
return dummy.next;
}
}
- 递归
反转二叉树
- 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public TreeNode invertTree(TreeNode root) {
//递归函数的终止条件,节点为空时返回
if(root==null) {
return null;
}
//下面三句是将当前节点的左右子树交换
TreeNode tmp = root.right;
root.right = root.left;
root.left = tmp;
//递归交换当前节点的 左子树
invertTree(root.left);
//递归交换当前节点的 右子树
invertTree(root.right);
//函数返回时就表示当前这个节点,以及它的左右子树
//都已经交换完了
return root;
}
- 递归
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Comment
WalineFacebook Comments