10.代码的鲁棒性(4)

题一：【链表中倒数第k个节点】

输入一个链表，输出该链表中倒数第k个结点。

分析：快慢指针，快指针比慢指针先走k-1步，当快指针走到末尾时，慢指针之乡的位置就是倒数第k个节点；

 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三个指针，分别指向当前节点的前一个结点、当前节点、当前节点的后一个节点；

 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 }

 

 

题三：【合并两个排序的链表】

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

分析：将第二个链表插入到第一个链表中，如果第二个链表中节点list2的值大于第一个链表中节点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!=null25         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.icode9.com/content-4-595801.html