|
題一：【鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)】 輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。 分析：快慢指針，快指針比慢指針先走k-1步，當(dāng)快指針走到末尾時(shí)，慢指針之鄉(xiāng)的位置就是倒數(shù)第k個(gè)節(jié)點(diǎn)； 1 /*
2 public class ListNode {
3 int val;
4 ListNode next = null;
5
6 ListNode(int val) {
7 this.val = val;
8 }
9 }*/
10 public class Solution {
11 public ListNode FindKthToTail(ListNode head,int k) {
12 if(head==null||k<=0) return null;
13 ListNode fNode = head;
14 for(int i=1;i<k;i ){
15 fNode = fNode.next;
16 if(fNode==null) return null;
17 }
18 while(fNode.next!=null){
19 head = head.next;
20 fNode = fNode.next;
21 }
22 return head;
23 }
24 }
? 題二：【反轉(zhuǎn)鏈表】 ?輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭。 分析：設(shè)置pre、cur、next三個(gè)指針，分別指向當(dāng)前節(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)、當(dāng)前節(jié)點(diǎn)、當(dāng)前節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)； 1 /*
2 public class ListNode {
3 int val;
4 ListNode next = null;
5
6 ListNode(int val) {
7 this.val = val;
8 }
9 }*/
10 public class Solution {
11 public ListNode ReverseList(ListNode head) {
12 ListNode pre=null;
13 ListNode next=null;
14 ListNode cur = head;
15 while(cur!=null){
16 next=cur.next;
17 cur.next=pre;
18 pre=cur;
19 cur=next;
20 }
21 return pre;
22 }
23 }
? ? 題三：【合并兩個(gè)排序的鏈表】 輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。 分析：將第二個(gè)鏈表插入到第一個(gè)鏈表中，如果第二個(gè)鏈表中節(jié)點(diǎn)list2的值大于第一個(gè)鏈表中節(jié)點(diǎn)list1的值且小于第一個(gè)鏈表的下一個(gè)結(jié)點(diǎn)list1.next的值，則將list2插入到list1和list1.next中。 1 /*
2 public class ListNode {
3 int val;
4 ListNode next = null;
5
6 ListNode(int val) {
7 this.val = val;
8 }
9 }*/
10 public class Solution {
11 public ListNode Merge(ListNode list1,ListNode list2) {
12 if(list1==null) return list2;
13 if(list2==null) return list1;
14 ListNode head = list1;
15 while(list1!=null&&list2!=null){
16 if(list1.val<=list2.val&&(list1.next==null||list1.next.val>list2.val)){
17 ListNode next2 = list2.next;//畫個(gè)圖就清晰了
18 list2.next = list1.next;
19 list1.next = list2;
20 list2 = next2;
21 list1 = list1.next;
22 }else{
23 list1 = list1.next;
24 }
25 }
26 return head;
27 }
28 }
? 法二：遞歸 1 /*
2 public class ListNode {
3 int val;
4 ListNode next = null;
5
6 ListNode(int val) {
7 this.val = val;
8 }
9 }*/
10 public class Solution {
11 public ListNode Merge(ListNode list1,ListNode list2) {
12 if(list1==null) return list2;
13 if(list2==null) return list1;
14 if(list1.val<=list2.val){
15 list1.next = Merge(list1.next,list2);
16 return list1;
17 }else{
18 list2.next = Merge(list1,list2.next);
19 return list2;
20 }
21 }
22 }
? 題四：【樹的子結(jié)構(gòu)】 ?輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個(gè)樹的子結(jié)構(gòu)） ?分析：使用遞歸，先查找B樹在A中的位置（遞歸方法一），然后遞歸查找A.left,B.left和A.right,B.right（遞歸方法二）； ? 1 /**
2 public class TreeNode {
3 int val = 0;
4 TreeNode left = null;
5 TreeNode right = null;
6
7 public TreeNode(int val) {
8 this.val = val;
9
10 }
11
12 }
13 */
14 public class Solution {
15 public boolean HasSubtree(TreeNode root1,TreeNode root2) {
16 if(root1==null||root2==null) return false;
17 return isSubtree(root1,root2)//root1.val=root2.val,下面兩個(gè)是不等情況下進(jìn)行
18 ||HasSubtree(root1.left,root2)//從root1左子樹找
19 ||HasSubtree(root1.right,root2);//從root1右子樹找
20 }
21
22 public boolean isSubtree(TreeNode root1, TreeNode root2){
23 if(root2==null) return true;
24 if(root1==null)return false;//root1==null&&root2!=null
25 if(root1.val==root2.val){
26 return isSubtree(root1.left,root2.left)&&isSubtree(root1.right,root2.right);
27 }else{
28 return false;
29 }
30 }
31 }
? ? ? ? ? ? ? ? ? ? ? ? ? 來源：https://www./content-4-595801.html |
|
|
