packageLinkedListSummary;
importjava.util.HashMap;
importjava.util.Stack;
/**
*?http://blog.csdn.net/luckyxiaoqiang/article/details/7393134?輕松搞定面試中的鏈表題目
*?http://www.cnblogs.com/jax/archive/2009/12/11/1621504.html?算法大全(1)單鏈表
*
*?目錄：
*?1.?求單鏈表中結點的個數:?getListLength
*?2.?將單鏈表反轉:?reverseList(遍歷)，reverseListRec(遞歸)
*?3.?查找單鏈表中的倒數第K個結點(k?>?0):?reGetKthNode
*?4.?查找單鏈表的中間結點:?getMiddleNode
*?5.?從尾到頭打印單鏈表:?reversePrintListStack，reversePrintListRec(遞歸)
*?6.?已知兩個單鏈表pHead1?和pHead2?各自有序，把它們合并成一個鏈表依然有序:?mergeSortedList,?mergeSortedListRec
*?7.?判斷一個單鏈表中是否有環:?hasCycle
*?8.?判斷兩個單鏈表是否相交:?isIntersect
*?9.?求兩個單鏈表相交的第一個節點:?getFirstCommonNode
*?10.?已知一個單鏈表中存在環，求進入環中的第一個節點:?getFirstNodeInCycle,?getFirstNodeInCycleHashMap
*?11.?給出一單鏈表頭指針pHead和一節點指針pToBeDeleted，O(1)時間復雜度刪除節點pToBeDeleted:?delete
*
*/
publicclassDemo?{
publicstaticvoidmain(String[]?args)?{
Node?n1?=?newNode(1);
Node?n2?=?newNode(2);
Node?n3?=?newNode(3);
Node?n4?=?newNode(4);
Node?n5?=?newNode(5);
n1.next?=?n2;
n2.next?=?n3;
n3.next?=?n4;
n4.next?=?n5;
printList(n1);
//??????System.out.println(getListLength(n1));
//??????Node?head?=?reverseList(n1);
//??????Node?head?=?reverseListRec(n1);
//??????printList(head);
Node?x?=?reGetKthNode(n1,?2);
System.out.println(x.val);
reGetKthNodeRec(n1,?2);
//??????x?=?getMiddleNode(head);
//??????System.out.println(x.val);
//??????System.out.println("reversePrintListStack:");
//??????reversePrintListStack(head);
//??????System.out.println("reversePrintListRec:");
//??????reversePrintListRec(head);
}
//??public?static?void?main(String[]?args)?{
//??????Node?n1?=?new?Node(1);
//??????Node?n2?=?new?Node(3);
//??????Node?n3?=?new?Node(5);
//??????n1.next?=?n2;
//??????n2.next?=?n3;
//
//??????Node?m1?=?new?Node(1);
//??????Node?m2?=?new?Node(4);
//??????Node?m3?=?new?Node(6);
//??????m1.next?=?m2;
//??????m2.next?=?m3;
//
//
//??????Node?ret?=?mergeSortedList(n1,?m1);
//??????printList(ret);
//??}
privatestaticclassNode?{
intval;
Node?next;
publicNode(intval)?{
this.val?=?val;
}
}
publicstaticvoidprintList(Node?head)?{
while(head?!=null)?{
System.out.print(head.val?+?"?");
head?=?head.next;
}
System.out.println();
}
//?求單鏈表中結點的個數
//?注意檢查鏈表是否為空。時間復雜度為O(n)
publicstaticintgetListLength(Node?head)?{
//?注意頭結點為空情況
if(head?==null)?{
return0;
}
intlen?=0;
Node?cur?=?head;
while(cur?!=null)?{
len++;
cur?=?cur.next;
}
returnlen;
}
//?翻轉鏈表(遍歷)
//?從頭到尾遍歷原鏈表，每遍歷一個結點，
//?將其摘下放在新鏈表的最前端。
//?注意鏈表為空和只有一個結點的情況。時間復雜度為O(n)
publicstaticNode?reverseList(Node?head)?{
//?如果鏈表為空或只有一個節點，無需反轉，直接返回原鏈表表頭
if(head?==null||?head.next?==null)?{
returnhead;
}
Node?reHead?=?null;//?反轉后新鏈表指針
Node?cur?=?head;
while(cur?!=null)?{
Node?preCur?=?cur;??????//?用preCur保存住對要處理節點的引用
cur?=?cur.next;?????????????//?cur更新到下一個節點
preCur.next?=?reHead;???//?更新要處理節點的next引用
reHead?=?preCur;????????????//?reHead指向要處理節點的前一個節點
}
returnreHead;
}
//?翻轉遞歸(遞歸)
//?遞歸的精髓在于你就默認reverseListRec已經成功幫你解決了子問題了！但別去想如何解決的
//?現在只要處理當前node和子問題之間的關系。最后就能圓滿解決整個問題。
/*
head
1?->?2?->?3?->?4
head
1--------------
|
4?->?3?->?2????????????????????????????//?Node?reHead?=?reverseListRec(head.next);
reHead??????head.next
4?->?3?->?2?->?1????????????????????//?head.next.next?=?head;
reHead
4?->?3?->?2?->?1?->?null????????????//?head.next?=?null;
reHead
*/
publicstaticNode?reverseListRec(Node?head){
if(head?==null||?head.next?==null){
returnhead;
}
Node?reHead?=?reverseListRec(head.next);
head.next.next?=?head;??????//?把head接在reHead串的最后一個后面
head.next?=?null;//?防止循環鏈表
returnreHead;
}
/**
*?查找單鏈表中的倒數第K個結點(k?>?0)
*?最普遍的方法是，先統計單鏈表中結點的個數，然后再找到第(n-k)個結點。注意鏈表為空，k為0，k為1，k大于鏈表中節點個數時的情況
*?。時間復雜度為O(n)。代碼略。?這里主要講一下另一個思路，這種思路在其他題目中也會有應用。
*?主要思路就是使用兩個指針，先讓前面的指針走到正向第k個結點
*?，這樣前后兩個指針的距離差是k-1，之后前后兩個指針一起向前走，前面的指針走到最后一個結點時，后面指針所指結點就是倒數第k個結點
*/
publicstaticNode?reGetKthNode(Node?head,intk)?{
//?這里k的計數是從1開始，若k為0或鏈表為空返回null
if(k?==0||?head?==null)?{
returnnull;
}
Node?q?=?head;?//?q在p前面??p--q
Node?p?=?head;?//?p在q后面
//?讓q領先p距離k
while(k?>1&&?q?!=null)?{
q?=?q.next;
k--;
}
//?當節點數小于k，返回null
if(k?>1||?q?==null)?{
returnnull;
}
//?前后兩個指針一起走，直到前面的指針指向最后一個節點
while(q.next?!=null)?{
p?=?p.next;
q?=?q.next;
}
//?當前面的指針指向最后一個節點時，后面的指針指向倒數k個節點
returnp;
}
/**
*?遞歸打印出倒數第k位的值
*?@param?head
*?@param?dist
*/
staticintlevel?=0;
publicstaticvoidreGetKthNodeRec(Node?head,intk)?{
if(head?==null){
return;
}
if(k?==1){
return;
}
reGetKthNodeRec(head.next,?k);
level++;
if(level?==?k)?{
System.out.println(head.val);
}
}
//?查找單鏈表的中間結點
/**
*?此題可應用于上一題類似的思想。也是設置兩個指針，只不過這里是，兩個指針同時向前走，前面的指針每次走兩步，后面的指針每次走一步，
*?前面的指針走到最后一個結點時，后面的指針所指結點就是中間結點，即第(n/2+1)個結點。注意鏈表為空，鏈表結點個數為1和2的情況。時間復雜度O(n
*/
publicstaticNode?getMiddleNode(Node?head)?{
if(head?==null||?head.next?==null)?{
returnhead;
}
Node?q?=?head;??????//?p---q
Node?p?=?head;
//?前面指針每次走兩步，直到指向最后一個結點，后面指針每次走一步
while(q.next?!=null)?{
q?=?q.next;
p?=?p.next;
if(q.next?!=null)?{
q?=?q.next;
}
}
returnp;
}
/**
*?從尾到頭打印單鏈表
*?對于這種顛倒順序的問題，我們應該就會想到棧，后進先出。所以，這一題要么自己使用棧，要么讓系統使用棧，也就是遞歸。注意鏈表為空的情況
*?。時間復雜度為O(n)
*/
publicstaticvoidreversePrintListStack(Node?head)?{
Stack?s?=?newStack();
Node?cur?=?head;
while(cur?!=null)?{
s.push(cur);
cur?=?cur.next;
}
while(!s.empty())?{
cur?=?s.pop();
System.out.print(cur.val?+?"?");
}
System.out.println();
}
/**
*?從尾到頭打印鏈表，使用遞歸(優雅！)
*/
publicstaticvoidreversePrintListRec(Node?head)?{
if(head?==null)?{
return;
}?else{
reversePrintListRec(head.next);
System.out.print(head.val?+?"?");
}
}
/**
*?已知兩個單鏈表pHead1?和pHead2?各自有序，把它們合并成一個鏈表依然有序
*?這個類似歸并排序。尤其注意兩個鏈表都為空，和其中一個為空時的情況。只需要O(1)的空間。時間復雜度為O(max(len1,?len2))
*/
publicstaticNode?mergeSortedList(Node?head1,?Node?head2)?{
//?其中一個鏈表為空的情況，直接返回另一個鏈表頭，O(1)
if(head1?==null)?{
returnhead2;
}
if(head2?==null)?{
returnhead1;
}
Node?mergeHead?=?null;
//?先確定下來mergeHead是在哪里
if(head1.val?
mergeHead?=?head1;
head1?=?head1.next;?????????//?跳過已經合并了的元素
mergeHead.next?=?null;//?斷開mergeHead和后面的聯系
}?else{
mergeHead?=?head2;
head2?=?head2.next;
mergeHead.next?=?null;
}
Node?mergeCur?=?mergeHead;
while(head1?!=null&&?head2?!=null)?{
if(head1.val?
mergeCur.next?=?head1;???????//?把找到較小的元素合并到merge中
head1?=?head1.next;??????????????//?跳過已經合并了的元素
mergeCur?=?mergeCur.next;????//?找到下一個準備合并的元素
mergeCur.next?=?null;//?斷開mergeCur和后面的聯系
}?else{
mergeCur.next?=?head2;
head2?=?head2.next;
mergeCur?=?mergeCur.next;
mergeCur.next?=?null;
}
}
//?合并剩余的元素
if(head1?!=null)?{
mergeCur.next?=?head1;
}?elseif(head2?!=null)?{
mergeCur.next?=?head2;
}
returnmergeHead;
}
/**
*?遞歸合并兩鏈表(優雅！)
*/
publicstaticNode?mergeSortedListRec(Node?head1,?Node?head2)?{
if(head1?==null)?{
returnhead2;
}
if(head2?==null)?{
returnhead1;
}
Node?mergeHead?=?null;
if(head1.val?
mergeHead?=?head1;
//?連接已解決的子問題
mergeHead.next?=?mergeSortedListRec(head1.next,?head2);
}?else{
mergeHead?=?head2;
mergeHead.next?=?mergeSortedListRec(head1,?head2.next);
}
returnmergeHead;
}
/**
*?判斷一個單鏈表中是否有環
*?這里也是用到兩個指針。如果一個鏈表中有環，也就是說用一個指針去遍歷，是永遠走不到頭的。因此，我們可以用兩個指針去遍歷，一個指針一次走兩步
*?，一個指針一次走一步，如果有環，兩個指針肯定會在環中相遇。時間復雜度為O(n)
*/
publicstaticbooleanhasCycle(Node?head)?{
Node?fast?=?head;?//?快指針每次前進兩步
Node?slow?=?head;?//?慢指針每次前進一步
while(fast?!=null&&?fast.next?!=null)?{
fast?=?fast.next.next;
slow?=?slow.next;
if(fast?==?slow)?{//?相遇，存在環
returntrue;
}
}
returnfalse;
}
//?判斷兩個單鏈表是否相交
/**
*?如果兩個鏈表相交于某一節點，那么在這個相交節點之后的所有節點都是兩個鏈表所共有的。?也就是說，如果兩個鏈表相交，那么最后一個節點肯定是共有的。
*?先遍歷第一個鏈表，記住最后一個節點，然后遍歷第二個鏈表，?到最后一個節點時和第一個鏈表的最后一個節點做比較，如果相同，則相交，
*?否則不相交。時間復雜度為O(len1+len2)，因為只需要一個額外指針保存最后一個節點地址，?空間復雜度為O(1)
*/
publicstaticbooleanisIntersect(Node?head1,?Node?head2)?{
if(head1?==null||?head2?==null)?{
returnfalse;
}
Node?tail1?=?head1;
//?找到鏈表1的最后一個節點
while(tail1.next?!=null)?{
tail1?=?tail1.next;
}
Node?tail2?=?head2;
//?找到鏈表2的最后一個節點
while(tail2.next?!=null)?{
tail2?=?tail2.next;
}
returntail1?==?tail2;
}
/**
*?求兩個單鏈表相交的第一個節點?對第一個鏈表遍歷，計算長度len1，同時保存最后一個節點的地址。
*?對第二個鏈表遍歷，計算長度len2，同時檢查最后一個節點是否和第一個鏈表的最后一個節點相同，若不相同，不相交，結束。
*?兩個鏈表均從頭節點開始，假設len1大于len2
*?，那么將第一個鏈表先遍歷len1-len2個節點，此時兩個鏈表當前節點到第一個相交節點的距離就相等了，然后一起向后遍歷，直到兩個節點的地址相同。
*?時間復雜度，O(len1+len2)
*
*??????????????----????len2
*???????????????????|__________
*???????????????????|
*???????---------???len1
*???????|---|
*/
publicstaticNode?getFirstCommonNode(Node?head1,?Node?head2)?{
if(head1?==null||?head2?==null)?{
returnnull;
}
intlen1?=1;
Node?tail1?=?head1;
while(tail1.next?!=null)?{
tail1?=?tail1.next;
len1++;
}
intlen2?=1;
Node?tail2?=?head2;
while(tail2.next?!=null)?{
tail2?=?tail2.next;
len2++;
}
//?不相交直接返回NULL
if(tail1?!=?tail2)?{
returnnull;
}
Node?n1?=?head1;
Node?n2?=?head2;
//?略過較長鏈表多余的部分
if(len1?>?len2)?{
intk?=?len1?-?len2;
while(k?!=0)?{
n1?=?n1.next;
k--;
}
}?else{
intk?=?len2?-?len1;
while(k?!=0)?{
n2?=?n2.next;
k--;
}
}
//?一起向后遍歷，直到找到交點
while(n1?!=?n2)?{
n1?=?n1.next;
n2?=?n2.next;
}
returnn1;
}
/**
*?求進入環中的第一個節點?用快慢指針做(本題用了Crack?the?Coding?Interview的解法，因為更簡潔易懂！)
*/
publicstaticNode?getFirstNodeInCycle(Node?head)?{
Node?slow?=?head;
Node?fast?=?head;
//?1)?找到快慢指針相遇點
while(fast?!=null&&?fast.next?!=null)?{
slow?=?slow.next;
fast?=?fast.next.next;
if(slow?==?fast)?{//?Collision
break;
}
}
//?錯誤檢查，這是沒有環的情況
if(fast?==null||?fast.next?==null)?{
returnnull;
}
//?2)現在，相遇點離環的開始處的距離等于鏈表頭到環開始處的距離，
//?這樣，我們把慢指針放在鏈表頭，快指針保持在相遇點，然后
//?同速度前進，再次相遇點就是環的開始處！
slow?=?head;
while(slow?!=?fast)?{
slow?=?slow.next;
fast?=?fast.next;
}
//?再次相遇點就是環的開始處
returnfast;
}
/**
*?求進入環中的第一個節點?用HashMap做?一個無環的鏈表，它每個結點的地址都是不一樣的。
*?但如果有環，指針沿著鏈表移動，那這個指針最終會指向一個已經出現過的地址?以地址為哈希表的鍵值，每出現一個地址，就將該鍵值對應的實值置為true。
*?那么當某個鍵值對應的實值已經為true時，說明這個地址之前已經出現過了，?直接返回它就OK了
*/
publicstaticNode?getFirstNodeInCycleHashMap(Node?head)?{
HashMap?map?=?newHashMap();
while(head?!=null)?{
if(map.get(head)?==true)?{
returnhead;//?這個地址之前已經出現過了，就是環的開始處
}?else{
map.put(head,?true);
head?=?head.next;
}
}
returnhead;
}
/**
*?給出一單鏈表頭指針head和一節點指針toBeDeleted，O(1)時間復雜度刪除節點tBeDeleted
*?對于刪除節點，我們普通的思路就是讓該節點的前一個節點指向該節點的下一個節點
*?，這種情況需要遍歷找到該節點的前一個節點，時間復雜度為O(n)。對于鏈表，
*?鏈表中的每個節點結構都是一樣的，所以我們可以把該節點的下一個節點的數據復制到該節點
*?，然后刪除下一個節點即可。要注意最后一個節點的情況，這個時候只能用常見的方法來操作，先找到前一個節點，但總體的平均時間復雜度還是O(1)
*/
publicvoiddelete(Node?head,?Node?toDelete){
if(toDelete?==null){
return;
}
if(toDelete.next?!=null){//?要刪除的是一個中間節點
toDelete.val?=?toDelete.next.val;???????//?將下一個節點的數據復制到本節點!
toDelete.next?=?toDelete.next.next;
}
else{//?要刪除的是最后一個節點！
if(head?==?toDelete){//?鏈表中只有一個節點的情況
head?=?null;
}else{
Node?node?=?head;
while(node.next?!=?toDelete){//?找到倒數第二個節點
node?=?node.next;
}
node.next?=?null;
}
}
}
}
和OGNL表達式)
_PHP教程)
