LeetCode 解題筆記(Linked List類型題目) - HackMD

var mergeTwoLists = function(l1, l2) { // 儲存結果的ListNode var result = new ListNode(0); // 目前Node位置var c = result; while(l1 !== null && l2 !==null){ // ...       Published LinkedwithGitHub Like Bookmark Subscribe Edit #LeetCode解題筆記(LinkedList類型題目) 解題時要注意的重點 1.一題多解，找不同的思維；可以看討論區的解題方法 2.不要盲目刷題，至少要帶走一些想法 3.精通一種解法；某些題型適合某一種演算法，可以做統整 4.定義題目內容與輸出的結果；例如考官到底要什麼；題目給的例子是不是分類過的array   [影片來源](https://www.youtube.com/watch?v=NdWYxz3izH4) ##[難度Easy]類型：LinkedList ###021.MergeTwoSortedLists [題目網址](https://leetcode.com/problems/merge-two-sorted-lists/) >將兩個LinkedList合併，而且順序要從小到大 >範例：[1,2,2,3]+[1,3]=[1,1,2,2,3,3] ``` varmergeTwoLists=function(l1,l2){ //儲存結果的ListNode varresult=newListNode(0); //目前Node位置 varc=result; while(l1!==null&&l2!==null){ //l1,l2較小的數加入result if(l1.val>l2.val){ c.next=l2; l2=l2.next; }else{ c.next=l1; l1=l1.next } c=c.next; } //將l1,l2剩下的Node加到result if(l1!==null){ c.next=l1; } if(l2!==null){ c.next=l2; } returnresult.next }; ``` 1.先建立一個LinkedList，將要返回的內容串接在後面 2.先比較兩個LinkedListl1、l2head的value大小，將較小的加入result(c.next=l1或l2) 3.加入之後，將LinkedList串接數減少一個(l1=l1.next、l2=l2.next) 4.繼續串接下一個(c=c.next)，直到l1、l2其中一個沒有node可以串接(l1!==null&&l2!==null) 5.將剩下的list串接上去 [作法來源](https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/21md.html) [同樣解法1](https://leetcode.com/problems/merge-two-sorted-lists/discuss/341711/Clean-Javascript) ``` varmergeTwoLists=function(l1,l2){ letres=newListNode(); letcur=res; while(l1&&l2){ if(l1.val<=l2.val){ cur.next=newListNode(l1.val); l1=l1.next; cur=cur.next; } else{ cur.next=newListNode(l2.val); l2=l2.next; cur=cur.next; } } cur.next=l1||l2; returnres.next; }; ``` [同樣解法2，但比較簡潔](https://leetcode.com/problems/merge-two-sorted-lists/discuss/167585/javascript-clean-solution) ###083.RemoveDuplicatesfromSortedList [題目網址](https://leetcode.com/problems/remove-duplicates-from-sorted-list/) >給予1個個LinkedList，移除重複的部分 >Input:1->1->2->3->3；Output:1->2->3 ``` vardeleteDuplicates=function(head){ if(!head||!head.next)returnhead letcurrent=head while(current.next){ if(current.val===current.next.val){ current.next=current.next.next }else{ current=current.next } } returnhead }; ``` 1.如果給予的List什麼都沒有，或只有一個node，那就直接回傳head 2.接著開始串接，將初始值current設定為Head，當下一個值相同時，串接到下下一個node，不相同時，繼續下一個node，直到current.next為null為止 3.[參考來源](https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/83md.html) ``` vardeleteDuplicates=function(head){ if(!head){ returnhead; } varnode=head.next; varprev=head; while(node){ if(node.val!==prev.val){ prev.next=node; prev=node; } node=node.next; } prev.next=null; returnhead }; ``` 1.如果給予的List什麼都沒有，或只有一個node，那就直接回傳head 2.不停歷遍所有node(while(node)、node=node.next)，如果遇到值不同的，就更新next，與當下歷遍pre的位置[(參考來源)](https://leetcode.com/problems/remove-duplicates-from-sorted-list/discuss/28706/Javascript-Solution) ###141.LinkedListCycle [題目網址](https://leetcode.com/problems/linked-list-cycle/) >給予一個個LinkedList，裡面的數值可能會重複，判斷這個list是不是一個循環的list； >關於怎樣循環，請見題目內的說明 ``` varhasCycle=function(head){ letcur=head if(!cur||!cur.next)returnfalse //key:valuevalue:nextvalue constobj={} while(cur.next){ if(obj[cur.val]===cur.next.val)returntrue obj[cur.val]=cur.next.val cur=cur.next } returnfalse }; ``` 1.先判斷有沒有list或是不是只有一個node，如果是的話，那就不能循環，回傳fale 2.建立一個object，key紀錄current當下歷遍node的值，value則是下一個node的值 3.開始歷遍node，每一次歷遍時，紀錄數值到object中，當發現貯存的key與value存在時，代表已經開始循環了，回傳true ``` varhasCycle=function(head){ if(head==null||head.next==null){ returnfalse; } varnode=head; while(node!=null){ if(node.flag){ returntrue; } //標記這個node已經跑過 node.flag=true; node=node.next; } returnfalse; } ``` 每經過一個node就標記，如果有標記，代表已經開始循環了 ``` varhasCycle=function(head){ if(head==null||head.next==null){ returnfalse; } varslow=head.next; varfast=head.next.next; if(fast==null){ returnfalse; } while(slow!=fast){ if(fast.next==null){ returnfalse; } slow=slow.next; fast=fast.next.next; if(slow==null||fast==null){ returnfalse; } } returntrue; } ``` [快慢指針做法](https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/141md.html) ######tags:`javascript``LeetCode``LinkedList` × Signin Email Password Forgotpassword or Byclickingbelow,youagreetoourtermsofservice. SigninviaFacebook SigninviaTwitter SigninviaGitHub SigninviaDropbox SigninviaGoogle NewtoHackMD?Signup