鏈表系列題目

1.打印兩個有序鏈表的公共部分

【題目】給定兩個有序鏈表的頭指針head1和head2搁痛，打印兩個鏈表的公共部分长搀。例如：
【思路】因為鏈表有序，兩個指針同時開始鸡典，一一進行比較源请，誰小誰就往后移動，若相等就打印彻况，然后一起向后移動谁尸。

2.判斷一個鏈表是否為回文結(jié)構(gòu)

【題目】給定一個鏈表的頭節(jié)點head，請判斷該鏈表是否為回文結(jié)構(gòu)疗垛。例如：
1->2->1症汹，返回true。
1->2->2->1贷腕，返回true背镇。
15->6->15，返回true泽裳。
1->2->3瞒斩，返回false。
【思路】

方法一：遍歷鏈表涮总，將值依次入棧胸囱，因為回文就是正序遍歷=逆序遍歷；再次遍歷鏈表瀑梗，同時棧依次彈出烹笔，如果一直都是相等的，就是回文抛丽。
方法二：（棧的空間減少了一半）兩個指針谤职，一快一慢，即一個走一步亿鲜，一個走兩步允蜈；當快指針走完之后，慢指針在此之后遍歷的數(shù)字依次入棧蒿柳；然后再次從頭遍歷指針饶套，同時棧依次彈出，如果一直都是相等的垒探，就是回文妓蛮。

【進階】如果鏈表長度為N，時間復雜度達到O(N)圾叼，額外空間復雜度達到O(1)蛤克。
【思路】兩個指針扔仓，一快一慢，即一個走一步咖耘，一個走兩步；當快指針走完之后撬码，慢指針在此之后遍歷的數(shù)字進行reverse儿倒；然后從兩頭同時開始遍歷，如果一直都是相等的呜笑，就是回文夫否。

3.將單向鏈表按某值劃分成左邊小、中間相等叫胁、右邊大的形式

【題目】

給定一個單向鏈表的頭節(jié)點head凰慈，節(jié)點的值類型是整型，再給定一個整數(shù)pivot驼鹅。
實現(xiàn)一個調(diào)整鏈表的函數(shù)微谓，將鏈表調(diào)整為左部分都是值小于pivot的節(jié)點，中間部分都是值等于pivot的節(jié)點输钩，右部分都是值大于pivot的節(jié)點豺型。除這個要求外，對調(diào)整后的節(jié)點順序沒有更多的要求买乃。
例如：鏈表9->0->4->5->1姻氨，pivot=3。調(diào)整后鏈表可以是1->0->4->9->5剪验，也可以是0->1->9->5->4肴焊。
總之，滿足左部分都是小于3的節(jié)點功戚，中間部分都是等于3的節(jié)點（本例中這個部分為空）娶眷，右部分都是大于3的節(jié)點即可。對某部分內(nèi)部的節(jié)點順序不做要求疫铜。

【思路】

需要考慮某一塊沒有的情況茂浮。
方法一：準備三個隊列，遍歷鏈表壳咕，將節(jié)點入相應的隊列中席揽，然后再依次出隊列即可。
方法二：遍歷鏈表谓厘，分別找到第一個小于幌羞、等于和大于pivot的節(jié)點；然后將三個節(jié)點分別作為頭結(jié)點竟稳，遇到相應的節(jié)點就放入其中属桦；最后將三個鏈表的首尾相連即可熊痴。

4.復制含有隨機指針節(jié)點的鏈表

【題目】一種特殊的鏈表節(jié)點類描述如下：

public class Node {
  public int value;
  public Node next;
  public Node rand;
  public Node(int data) {
    this.value = data;
  }
}

Node類中的value是節(jié)點值，next指針和正常單鏈表中next指針的意義一樣聂宾，都指向下一個節(jié)點果善，rand指針是Node類中新增的指針，這個指針可能指向鏈表中的任意一個節(jié)點系谐，也可能指向null巾陕。
給定一個由Node節(jié)點類型組成的無環(huán)單鏈表的頭節(jié)點head，請實現(xiàn)一個函數(shù)完成這個鏈表中所有結(jié)構(gòu)的復制纪他，并返回復制的新鏈表的頭節(jié)點鄙煤。

【進階】不使用額外的數(shù)據(jù)結(jié)構(gòu)，只用有限幾個變量茶袒，且在時間復雜度為O(N)內(nèi)完成原問題要實現(xiàn)的函數(shù)梯刚。
【思路】

方法一：經(jīng)典解法，用map
方法二：克隆節(jié)點的時候薪寓，就將其放在老節(jié)點的后面亡资，克隆節(jié)點的random指向相對應老節(jié)點的random.next。然后進行分離向叉，得到克隆鏈表沟于，分離的時候不需要考慮random指針。

5.兩個單鏈表相交的一系列問題

【題目】

在本題中植康，單鏈表可能有環(huán)旷太，也可能無環(huán)。給定兩個單鏈表的頭節(jié)點head1和head2销睁，這兩個鏈表可能相交供璧，也可能不相交。
請實現(xiàn)一個函數(shù)冻记，如果兩個鏈表相交睡毒，請返回相交的第一個節(jié)點；如果不相交冗栗，返回null即可演顾。

【要求】如果鏈表1的長度為N，鏈表2的長度為M隅居，時間復雜度請達到O(N+M)钠至，額外空間復雜度請達到O(1)。
【思路】

判斷鏈表是否有環(huán)胎源，如果有環(huán)棉钧，返回第一個入環(huán)的節(jié)點。
- 方法一：遍歷鏈表涕蚤，將每個節(jié)點加入到map里宪卿，如果發(fā)現(xiàn)有一個節(jié)點再加入map前就已經(jīng)存在于map中的诵，說明有環(huán)，該節(jié)點即為入環(huán)節(jié)點佑钾；如果最后走到null了西疤，說明無環(huán)。
- 方法二：兩個指針休溶，一快一慢瘪阁，即一個走一步，一個走兩步邮偎。如果無環(huán)，那么快指針一定會走到結(jié)尾义黎；如果有環(huán)禾进，那么快指針和慢指針一定會在環(huán)里相遇，相遇后廉涕，快指針回到head節(jié)點泻云，然后快指針和慢指針都變?yōu)槊看巫咭徊剑瑫r開始走狐蜕，一定會在入環(huán)節(jié)點相遇（數(shù)學結(jié)論）宠纯。
二者相交分為三種情況
- 情況一：兩個單鏈表都無環(huán)。首先獲取兩個鏈表的長度层释，求得差值；用兩個指針，長度長的鏈表指針先走差值的步數(shù)工秩，然后再同時走涵妥；如果last1=last2說明它們一定相交，否則不相交乖寒。
- 情況二：一個鏈表有環(huán)猴蹂，一個鏈表無環(huán)，絕對不可能相交楣嘁。因為一個節(jié)點只能有一個next磅轻。
- 情況三：兩個鏈表都有環(huán)。
  - 兩個鏈表在環(huán)出現(xiàn)之前就相交了逐虚，之后一直相交聋溜。loop1=loop2，即兩個鏈表的入環(huán)節(jié)點相同叭爱，則相交勤婚。用兩個指針，長度長的鏈表指針先走差值的步數(shù)涤伐，然后再同時走馒胆；如果兩個鏈表的入環(huán)節(jié)點都不為空且相等缨称，則相交。
  - 兩個鏈表只共享環(huán)祝迂。loop1在環(huán)中走的時候遇到了loop2睦尽，但不相等。

6.反轉(zhuǎn)單向和雙向鏈表

【題目】分別實現(xiàn)反轉(zhuǎn)單向鏈表和反轉(zhuǎn)雙向鏈表的函數(shù)型雳。
【要求】如果鏈表長度為N当凡，時間復雜度要求為O(N)，額外空間復雜度要求為O(1)纠俭。
【思路】可以用椦亓浚或者原地反轉(zhuǎn)。