題一：【鏈表中倒數(shù)第k個節(jié)點】
輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。
分析：快慢指針，快指針比慢指針先走k-1步，當(dāng)快指針走到末尾時，慢指針之鄉(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 }?
題二：【反轉(zhuǎn)鏈表】
?輸入一個鏈表，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭。
分析：設(shè)置pre、cur、next三個指針，分別指向當(dāng)前節(jié)點的前一個結(jié)點、當(dāng)前節(jié)點、當(dāng)前節(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 }?
?
題三：【合并兩個排序的鏈表】
輸入兩個單調(diào)遞增的鏈表，輸出兩個鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。
分析：將第二個鏈表插入到第一個鏈表中，如果第二個鏈表中節(jié)點list2的值大于第一個鏈表中節(jié)點list1的值且小于第一個鏈表的下一個結(jié)點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 }?
題四：【樹的子結(jié)構(gòu)】
?輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個樹的子結(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,下面兩個是不等情況下進(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!=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