單鏈表由一個(gè)個(gè)節(jié)點(diǎn)（Node）組成儡率，引用LeetCode里對(duì)單鏈表節(jié)點(diǎn)的表示：
<pre>
/**
- Definition for singly-linked list.
- class ListNode {
- int val;
- ListNode next;
- ListNode(int x) {
val = x;next = null;- }
- }
*/
</pre>
每個(gè)節(jié)點(diǎn)里包含儲(chǔ)存的內(nèi)容及下一個(gè)節(jié)點(diǎn)的引用身弊，這樣熄捍，獲得一個(gè)頭結(jié)點(diǎn)（head），就可以對(duì)其他任意節(jié)點(diǎn)進(jìn)行操作廓潜。
以下是一些單鏈表經(jīng)典題抵皱，LeetCode上都有。
1.判斷是否有環(huán)
可以用哈希表（HashSet）通過(guò)判重的方式解決辩蛋，也可以用一快一慢兩個(gè)指針來(lái)解決呻畸，這樣空間復(fù)雜度只有O(1)。具體思想是悼院，快指針每次移動(dòng)2伤为，慢指針每次移動(dòng)1，如果有環(huán)据途，那么快指針在某個(gè)時(shí)刻會(huì)追趕上慢指針钮呀。注意初始化時(shí)要讓快指針先移一格，否則最開(kāi)始快慢指針就會(huì)重合昨凡。
<pre>
public boolean hasCycle(ListNode head) {
if(head == null) return false;
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow) return true;
}
return false;
}</pre>
那么環(huán)從哪里開(kāi)始呢？假設(shè)慢指針從頭結(jié)點(diǎn)到環(huán)起始處需要走A步蚁署，再走B步與快指針相遇便脊。此時(shí)快指針走了2A+2B比慢指針多走一圈N，2A + 2B = N + A + B光戈。
由此得出 N = A + B哪痰。
慢指針已經(jīng)走了一圈中的B遂赠，再走A步又回到環(huán)起始處，而A正是從頭結(jié)點(diǎn)到環(huán)起始處的步數(shù)晌杰，用另一個(gè)指針從頭結(jié)點(diǎn)開(kāi)始與慢指針同步走跷睦，相遇處即為環(huán)起始處。
<pre>
public ListNode detectCycle(ListNode head) {
if(head == null) return null;
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
ListNode start = head;
while(start != slow){
start = start.next;
slow = slow.next;
}
return start;
}
}
return null;
}
</pre>
</br>
2.反轉(zhuǎn)鏈表
設(shè)置前后兩個(gè)指針肋演，每次讓后指針的next指向前指針抑诸，然后兩個(gè)指針都往后挪一位。注意前指針應(yīng)初始化為null爹殊，應(yīng)設(shè)置一個(gè)臨時(shí)變量?jī)?chǔ)存后指針的后一位以支持挪動(dòng)蜕乡。
<pre>
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode curr = head;
while(curr != null){
ListNode next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return pre;
}
</pre>
</br>
3.合并兩個(gè)有序單鏈表
實(shí)現(xiàn)思想就是用small，big兩個(gè)指針來(lái)分別指向兩個(gè)鏈表中當(dāng)前節(jié)點(diǎn)值較小和較大的梗夸，如果small的下一個(gè)節(jié)點(diǎn)比big大了层玲，就把small的next指向big，然后big指向原先的small鏈表元素反症。
<pre>
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode small = null;
ListNode big = null;
if(l1.val > l2.val){
small = l2;
big = l1;
}else{
small = l1;
big = l2;
}
ListNode head = small;
while(small.next != null && big != null){
if(small.next.val > big.val){
ListNode temp = small.next;
small.next = big;
small = big;
big = temp;
}else{
small = small.next;
}
}
small.next = big;
return head;
}
</pre>
看了下LeetCode其他人答案發(fā)現(xiàn)還可以遞歸解決辛块，于是順手也寫(xiě)了個(gè)，確實(shí)簡(jiǎn)潔不少铅碍。
<pre>
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode head = null;
if(l1.val < l2.val){
head = l1;
head.next = mergeTwoLists(l1.next,l2);
}else{
head = l2;
head.next = mergeTwoLists(l1,l2.next);
}
return head;
}
</pre>
