链表中倒数第k个节点
剑指 Offer 22. 链表中倒数第k个节点 - 力扣（Leetcode）
题目要求
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
例子：
1
2
3
| 给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
|
思路分析
求出链表长度size，那么倒数第k个值的前一个值，使用for循环的条件为i<size-k，找到k的前一个值的位置，让temp=temp.next输出，即为我们要找的倒数第k个值。
代码实现
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
|
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
if(head.next==null){
return head;
}
ListNode temp = head;
int size = 0;
while(head!=null){
size++;
head = head.next;
}
if(k<=0 || k>size){
return null;
}
for(int i=0;i<size-k;i++){
temp = temp.next;
}
return temp;
}
}
|
反转链表
剑指 Offer 24. 反转链表 - 力扣（Leetcode）
题目要求
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
例子：
1
2
| 输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
|
提示：
0 <= 节点个数 <= 5000
思路分析
递归
- 定义辅助变量，递归链表
head.next。
- head指向的节点指向head本身。
- head指向null。
原地反转
- 先定义一个节点 ListNode() reverseNode = new ListNode();
- 从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表的最前端；
- 最后返回reverseNode.next即可;
代码实现
递归 空间：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null ||head.next == null){
return head;
}
ListNode temp = reverseList(head.next);
head.next.next = head;
head.next = null;
return temp;
}
}
|
原地反转 空间：O(1)
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
|
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null ||head.next == null){
return head;
}
ListNode temp = head;
ListNode next = temp.next;
ListNode reverseNode = new ListNode(0);
while(temp!=null){
next = temp.next;
temp.next = reverseNode.next;
reverseNode.next = temp;
temp = next;
}
return reverseNode.next;
}
}
|
合并两个排序的链表
剑指 Offer 25. 合并两个排序的链表 - 力扣（Leetcode）
题目要求
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
例子：
1
2
| 输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
|
提示：
0 <= 链表长度 <= 1000
思路分析
定义一个新的链表merge和一个辅助指针ListNode temp=merge，不断比较链表l1和l2的值的大小，将较小的放入temp中，直到l1或者l2任意一个指向null，那就将temp.next指向另一个不为null的，最后将merge.next返回即可；
代码实现
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
|
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode merge = new ListNode(0);
ListNode temp = merge;
while(l1!=null && l2!=null){
if(l1.val>=l2.val){
temp.next = l2;
l2 = l2.next;
}else{
temp.next = l1;
l1 = l1.next;
}
temp = temp.next;
}
if(l1 == null){
temp.next = l2;
}else{
temp.next = l1;
}
return merge.next;
}
}
|
树的子结构
剑指 Offer 26. 树的子结构 - 力扣（Leetcode）
题目要求
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 给定的树 A:
3
/ \
4 5
/ \
1 2
给定的树 B：
4
/
1
|
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
例子：
1
2
3
4
5
| 输入：A = [1,2,3], B = [3,1]
输出：false
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
|
提示：
0 <= 节点个数 <= 10000
思路分析
递归进行以下步骤：
- 固定树A的头节点，判断树B是否为以A的子结构：
- 判断树B是否为树A的左子树的子结构：
- 判断树B是否为树A的右子树的子结构：
- 直到递归比对树A所有节点，且以上条件都不成立，那么返回false；
代码实现
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
|
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(A == null || B == null){
return false;
}
if(isSubTree(A,B)){
return true;
}
if(isSubStructure(A.left,B) || (isSubStructure(A.right,B))){
return true;
}
return false;
}
public boolean isSubTree(TreeNode TA,TreeNode TB){
if(TB==null){
return true;
}
if(TA==null){
return false;
}
if(TA.val != TB.val){
return false;
}
return isSubTree(TA.left,TB.left) &&
isSubTree(TA.right,TB.right);
}
}
|
二叉树的镜像
剑指 Offer 27. 二叉树的镜像 - 力扣（Leetcode）
题目要求
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 例如输入：
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出：
4
/ \
7 2
/ \ / \
9 6 3 1
|
例子：
1
2
| 输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
|
提示：
0 <= 节点个数 <= 1000
思路分析
通过递归获取左右子树，同时将left指向右子树，将right指向左子树；
代码实现
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
|
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null || (root.left==null && root.right==null)){
return root;
}
TreeNode left = mirrorTree(root.left);
TreeNode right = mirrorTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
|
微信
