56.刪除鏈表中重復(fù)結(jié)點(diǎn)
在一個排序的鏈表中派殷，存在重復(fù)的結(jié)點(diǎn)偿凭，請刪除該鏈表中重復(fù)的結(jié)點(diǎn)睁壁，重復(fù)的結(jié)點(diǎn)不保留氏身，返回鏈表頭指針寒屯。
例如荐捻，鏈表1->2->3->3->4->4->5 處理后為 1->2->5
這個題最開始的時候本人用的是三指針的方法，pre保留前一個位置寡夹，cur表示當(dāng)前位置处面，next表示下一個位置，當(dāng)cur.val==next.val時開始循環(huán)找到第一個不重復(fù)的點(diǎn)菩掏，然后將cur移動到這個位置魂角，實際寫起來又臭又長且由于三指針的存在對一些特殊情況很容易搞錯或遺漏，看到了newcode大神在github上的代碼智绸，恍然大悟野揪，對這種題用遞歸看起來更簡單，更加容易理解瞧栗，代碼也更簡潔斯稳；
思路如下
方法為public ListNode deleteDuplication(ListNode pHead){}
輸入為一個結(jié)點(diǎn)，返回的是以這個結(jié)點(diǎn)為頭結(jié)點(diǎn)的鏈表經(jīng)過刪除重復(fù)結(jié)點(diǎn)這個操作之后得到的鏈表的頭結(jié)點(diǎn)迹恐；
OK我們搞懂了這個函數(shù)干了件啥事兒挣惰，我們就可以直接把這個函數(shù)的返回值拿來用，即deleteDuplication(node)返回的是以node為頭結(jié)點(diǎn)的鏈表經(jīng)過刪除重復(fù)結(jié)點(diǎn)這一操作之后得到的頭結(jié)點(diǎn)殴边，我們先理解這一點(diǎn)憎茂，在抽象角度理解它，對遞歸大有裨益锤岸！然后再去實際的竖幔，方法體中的具體操作；
1.首先當(dāng)然還是判斷輸入是否為空是偷，或者輸入是否是單結(jié)點(diǎn)赏枚，對于這兩種情況我們都直接返回它本身即可亡驰；
2.由于我們要考察重復(fù)結(jié)點(diǎn)，所以我們需要一個指針指向的是pHead的下一個結(jié)點(diǎn)饿幅；
3.下一步凡辱，主函數(shù)體來了，如果pHead.val==next.val栗恩，就一直循環(huán)找到第一個和pHead的值不相等的結(jié)點(diǎn)透乾，例如1->1->2->3,找到的第一個與1不相等的結(jié)點(diǎn)是2，由于1,1我們都要刪除的磕秤，next此時也在2這位置了乳乌，那么怎么樣，我們的問題是不是相當(dāng)于以2這個結(jié)點(diǎn)為頭結(jié)點(diǎn)重新做這個方法市咆？
即返回值應(yīng)該用deleteDuplication(next)來操作汉操，我們把這個操作記做操作1；
如果不相等呢蒙兰，OK磷瘤，那么證明這個pHead這個結(jié)點(diǎn)不是重復(fù)結(jié)點(diǎn)，那么我們只需要確保它后面的結(jié)點(diǎn)是不含重復(fù)結(jié)點(diǎn)的鏈表即可搜变，上升到遞歸的宏觀角度來看采缚，我們怎么做pHead.next = deleteDuplication(pHead.next)即可，我們把這個操作記做操作2挠他；
其實在實際遞歸中這兩種遞歸方法都是交叉使用的扳抽，好就好在返回的是一個結(jié)點(diǎn)，而pHead.next這一操作又可以將遞歸返回的各結(jié)點(diǎn)之間相連接起來殖侵；
弄幾個具有特點(diǎn)的例子來分析下
1,1,1,1,1,1,1,1這個例子一進(jìn)來就是pHead.val==next.val直接用操作一贸呢，返回的是deleteDuplication(null),即返回null，正好符合
1,2,3,3,4,4,5拢军，首先pHead.next = deleteDuplication(2)贮尉，然后相當(dāng)于對2這個結(jié)點(diǎn)進(jìn)行操作，然后2不重復(fù)朴沿，又2.next = deleteDuplication(3)猜谚，返回的是deleteDuplication(4)，deleteDuplication（4）返回的又是deleteDuplication(5)赌渣，返回的即5本身魏铅，故1->2->5接上了，假設(shè)這個題最后一位是4而沒有5坚芜，也會遞歸到null,即1->2->null览芳，依然符合；
分析完了鸿竖，代碼如下
public ListNode deleteDuplication(ListNode pHead) {
if (pHead == null || pHead.next == null)
return pHead;
ListNode next = pHead.next;
if (pHead.val == next.val) {
while (next != null && pHead.val == next.val)
next = next.next;
return deleteDuplication(next);
} else {
pHead.next = deleteDuplication(pHead.next);
return pHead;
}
}
57.二叉樹的下一個結(jié)點(diǎn)
給定一個二叉樹和其中的一個結(jié)點(diǎn)沧竟，請找出中序遍歷順序的下一個結(jié)點(diǎn)并且返回铸敏。
注意，樹中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)悟泵，同時包含指向父結(jié)點(diǎn)的指針杈笔。
該題方仿照前面的二叉樹和鏈表的相互轉(zhuǎn)換即可
中序遍歷
1.左結(jié)點(diǎn)遞歸
2.do something
3.右結(jié)點(diǎn)遞歸
仿照這個順序，調(diào)整do something的位置即可得到前序和后序的方法
本題中需要注意根節(jié)點(diǎn)為給出糕非，需要用next指針來找到根節(jié)點(diǎn)
代碼如下
public class Solution {
//初始化一個標(biāo)志位來表示是否找到了當(dāng)前結(jié)點(diǎn)
private boolean flag = false;
//用一個結(jié)點(diǎn)res來存儲返回的結(jié)果
private TreeLinkNode res = null;
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
//由于存在指向父節(jié)點(diǎn)的next指針蒙具，所以我們先通過pNode找到根節(jié)點(diǎn)
TreeLinkNode cur = pNode;
while(cur.next!=null){
cur = cur.next;
}
//找到根節(jié)點(diǎn)了之后，這個題的做法就跟之前的二叉樹轉(zhuǎn)化為雙向鏈表一模一樣
mid_order(cur,pNode);
return res;
}
private void mid_order(TreeLinkNode node,TreeLinkNode pNode){
//遞歸到葉子結(jié)點(diǎn)的時候返回
if(node==null){
return;
}
//中序遍歷遞歸從左結(jié)點(diǎn)開始
mid_order(node.left,pNode);
//如果flag已經(jīng)為true了朽肥，證明前一個結(jié)點(diǎn)已經(jīng)是給定結(jié)點(diǎn)了
//此時只需把當(dāng)前結(jié)點(diǎn)賦給結(jié)點(diǎn)res即可禁筏，記得把flag再變?yōu)閒alse，不然會造成后面的錯誤
if(flag){
res = node;
flag = false;
}
//找到給定結(jié)點(diǎn)了衡招，就把flag變?yōu)閠rue篱昔，然后接著遞歸找到下一個結(jié)點(diǎn)
if(node == pNode){
flag = true;
}
mid_order(node.right,pNode);
}
}
