10.代碼的魯棒性(4)

印度阿三17 2019-12-12

展開全文

題一：【鏈表中倒數(shù)第k個節(jié)點】

輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結點。

分析：快慢指針，快指針比慢指針先走k-1步，當快指針走到末尾時，慢指針之鄉(xiāng)的位置就是倒數(shù)第k個節(jié)點；

 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 }

題二：【反轉鏈表】

?輸入一個鏈表，反轉鏈表后，輸出新鏈表的表頭。

分析：設置pre、cur、next三個指針，分別指向當前節(jié)點的前一個結點、當前節(jié)點、當前節(jié)點的后一個節(jié)點；

 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 }

題三：【合并兩個排序的鏈表】

輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規(guī)則。

分析：將第二個鏈表插入到第一個鏈表中，如果第二個鏈表中節(jié)點list2的值大于第一個鏈表中節(jié)點list1的值且小于第一個鏈表的下一個結點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;//畫個圖就清晰了
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 }

題四：【樹的子結構】

?輸入兩棵二叉樹A，B，判斷B是不是A的子結構。（ps：我們約定空樹不是任意一個樹的子結構）

?分析：使用遞歸，先查找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,下面兩個是不等情況下進行
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 }