1讯泣、翻轉(zhuǎn)鏈表
方法一：使用棧

public void solution(Node head){
    Stack stack=new Stack<>();
    while(head!=null){
        stack.push(head);
        head=head.next;
    }

    if(stack.pop()==null) return null;
    Node node=stack.pop();
    Node dummy=node;
 
    while(stack.isEmpty()){         
        Node tempNode=stack.pop();
        node.next=tempNode;         
        node=tempNode;          
    }

    node.next=null;
    return dummy;
}

解析：
先將鏈表的所有節(jié)點(diǎn)放入棧中并炮，彈出第一個(gè)節(jié)點(diǎn)作為新的頭節(jié)點(diǎn)鞠值，將彈出的剩下節(jié)點(diǎn)依次接到后面（第三個(gè)while循環(huán)臨時(shí)節(jié)點(diǎn)tempNode和當(dāng)前節(jié)點(diǎn)node交替賦值矿辽，直到取出棧中所有節(jié)點(diǎn)）node.next=tempNode將取出的臨時(shí)節(jié)點(diǎn)依次掛載到當(dāng)前節(jié)點(diǎn)的后面钉赁，當(dāng)取出棧中最后一個(gè)節(jié)點(diǎn)時(shí)需要斷掉依賴（否則會(huì)形成雙鏈）node.next=null

方法二：使用雙鏈表

public void solution(Node head){
    Node newHead=null;
    while(head!=null){                  
        Node temp=head.next;        
        head.next=newHead;          
        newHead=head;               
        head=temp;                  
    }
    return newHead;
}

解析：
其實(shí)就是將原鏈表的節(jié)點(diǎn)依次摘掉蹄殃，形成一條新鏈表。每次摘掉的節(jié)點(diǎn)作為新鏈表的頭節(jié)點(diǎn)（摘掉的節(jié)點(diǎn)接到新鏈表的前面）你踩，臨時(shí)節(jié)點(diǎn)temp和當(dāng)前節(jié)點(diǎn)head交替賦值就能取出全部節(jié)點(diǎn)诅岩，head.next=newhead將每次取出的當(dāng)前節(jié)點(diǎn)接在新鏈表最前面讳苦，newHead=head 更新新鏈表頭節(jié)點(diǎn)

兩種方法的區(qū)別：
棧解決 在放入棧中再取出節(jié)點(diǎn)這個(gè)過(guò)程中重新取出的節(jié)點(diǎn) 順序?qū)嶋H已經(jīng)被倒置 所以只需要按照鏈表添加方法那樣依次將取出節(jié)點(diǎn)接到后面即可
雙鏈表解決 將原鏈表節(jié)點(diǎn)依次摘掉，摘掉的節(jié)點(diǎn)依次接到新鏈表前面

方法三：使用遞歸

public Node<E> reverseList(Node head){
    if(head==null||head.next==null) return head;
    Node<E> newHead=reverseList(head.next);
    head.next.next=head;
    head.next=null;
    return newHead;
}   

解析：
reverseList(head.next)進(jìn)行遞歸調(diào)用吩谦，一直取到鏈表最后一個(gè)節(jié)點(diǎn)時(shí)跳出遞歸鸳谜，返回的是原鏈表最后一個(gè)節(jié)點(diǎn)，用來(lái)作為新鏈表的頭節(jié)點(diǎn)newHead式廷，每次遞歸結(jié)束的返回值都是newHead咐扭。head.next.next=head每次取出的當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)，head.next=null每次取出的當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)變?yōu)閚ull

2滑废、翻轉(zhuǎn)部分鏈表
將一個(gè)節(jié)點(diǎn)數(shù)為 size 鏈表 m 位置到 n 位置之間的區(qū)間反轉(zhuǎn)蝗肪，要求時(shí)間復(fù)雜度 O(n)O(n)，空間復(fù)雜度 O(1)O(1)

public Node<E> reverseList(Node<E> node,int m,int n){
    Node<E> preHead=node(-1);
    preHead.next=head;
    NOde<E> pre=preHead;
    for (int i=0;i<m-1;i++) {
        //pre指向修改區(qū)域前一個(gè)節(jié)點(diǎn)
        pre=preHead.next;
    }
    //保存前繼節(jié)點(diǎn)
    Node<E> preHead=pre;
    //翻轉(zhuǎn)鏈表的頭節(jié)點(diǎn)
    Node<E> cur=preHead.next;
    int i=0;
    //while(m<=n)
    while(i<n-m+1){  
        //保留下一個(gè)節(jié)點(diǎn)
        Node<E> temp=cur.next;
        //原鏈表摘掉的節(jié)點(diǎn)連接新鏈表頭節(jié)點(diǎn)
        cur.next=pre;
        //更新新鏈表頭節(jié)點(diǎn)
        pre=cur;
        //更新原鏈表下次需要摘掉的節(jié)點(diǎn)
        cur=temp;
        i++;
    }
    //鏈接后面
    preHead.next.next=cur;  
    //鏈接前面
    prehead.next=pre;  
    return newHead.next;
}

解析：
先找到需要翻轉(zhuǎn)區(qū)域的前一個(gè)節(jié)點(diǎn)pre作為新鏈表的頭節(jié)點(diǎn)preHead,然后按照雙鏈表翻轉(zhuǎn)的思路求解蠕趁，最后需要處理好翻轉(zhuǎn)完成后首尾節(jié)點(diǎn)的鏈接

3薛闪、鏈表中的節(jié)點(diǎn)每K個(gè)一組翻轉(zhuǎn)
將給出的鏈表中的節(jié)點(diǎn)每 k 個(gè)一組翻轉(zhuǎn)，返回翻轉(zhuǎn)后的鏈表
如果鏈表中的節(jié)點(diǎn)數(shù)不是 k 的倍數(shù)俺陋，將最后剩下的節(jié)點(diǎn)保持原樣

public static Node<E> iteratively(Node<E> head,int k){
    if(head==null&&head.next==null&&k<=1) return head;

    Node<E> dummy=node(-1);
    dummy.next=head;

    //前繼節(jié)點(diǎn)
    Node<E> prev=dummy;
    Node<E> start=dummy.next;
    Node<E> end=dummy.next;
    while(pre!=null){
        //找到本組最后一個(gè)節(jié)點(diǎn)
        for(int i=0;i<k-1&&end!=null;i++) end=end.next;
        //不足一組豁延，直接返回結(jié)果
        if(end==null) break;
        //緩存本組后繼節(jié)點(diǎn)
        Node<E> follow=end.next;
        //斷掉下一組的連接
        end.next=null;
        //反轉(zhuǎn)后start指針指向本組最后一個(gè)節(jié)點(diǎn),end指針指向頭節(jié)點(diǎn)
        //reverse返回新鏈表頭節(jié)點(diǎn)
        prev.next=reverse(start);
        //重新連接
        start.next=follow;
        //更新前繼節(jié)點(diǎn)
        prev=start;
    }
}
public static Node<E> reverse(Node<E> head){
    Node<E> cur=head;
    Node<E> newHead=null;
    while(head.next!=null){
        //緩存下一個(gè)節(jié)點(diǎn)
        Noede<E> temp=cur.next;
        //摘掉原鏈表的節(jié)點(diǎn)連接到新鏈表的最前面作為頭節(jié)點(diǎn)
        cur.next=newHead;
        //更新新鏈表
        newHead=cur;
        //更新原鏈表頭節(jié)點(diǎn)
        cur=temp;
    }
    return newHead;
}

解析：
需要用到四個(gè)指針
prev前繼節(jié)點(diǎn) 指向每K組節(jié)點(diǎn)鏈表的前一個(gè)節(jié)點(diǎn)
follow后繼節(jié)點(diǎn) 指向每K組節(jié)點(diǎn)鏈表的后一個(gè)節(jié)點(diǎn)
start開(kāi)始節(jié)點(diǎn)：翻轉(zhuǎn)前指向頭節(jié)點(diǎn)，翻轉(zhuǎn)后頭節(jié)點(diǎn)變?yōu)槲补?jié)點(diǎn)倔韭，start隨即改變指向?yàn)槲补?jié)點(diǎn)术浪，此時(shí)利用start鏈接后繼節(jié)點(diǎn)，利用start更新前繼節(jié)點(diǎn)
end結(jié)束節(jié)點(diǎn)：翻轉(zhuǎn)前指向尾節(jié)點(diǎn)寿酌，利用其斷掉下一組的連接胰苏，翻轉(zhuǎn)后隨即指向開(kāi)始節(jié)點(diǎn)

4、合并兩個(gè)排序的鏈表
輸入兩個(gè)遞增的鏈表醇疼，單個(gè)鏈表的長(zhǎng)度為n硕并，合并這兩個(gè)鏈表并使新鏈表中的節(jié)點(diǎn)仍然是遞增排序的

方法一：直接求解

public static Node<E> mergeList(Node<E> h1,Node<E> h2){
    Node<E> dummy=node(-1);
    Node<E> cur=dummy;

    while(h1!=null&||h2!=null){
        if(h1.val<=h2.val){
            cur.next=h1;
            h1=h1.next;
        }else{
            cur.next=h2;
            h2=h2.next;
        }
        //更新新鏈表尾節(jié)點(diǎn)
        cur=cur.next;
    }
    //新鏈表尾節(jié)點(diǎn)連接沒(méi)有比較完的鏈表
    cur.next=(h1==null?h2:h1);
    return dummy;
}

解析：
合并遞增判斷出需要節(jié)點(diǎn)間比較，讓指針不斷移動(dòng)指向每次比較后的新節(jié)點(diǎn)秧荆，再連接成串形成新鏈表
需要用到三個(gè)指針
cur開(kāi)始指向虛擬節(jié)點(diǎn)倔毙，指向每次比較結(jié)果節(jié)點(diǎn)值小的節(jié)點(diǎn)
h1開(kāi)始指向鏈表頭節(jié)點(diǎn)，若比較后是較小節(jié)點(diǎn)乙濒，則向后一節(jié)點(diǎn)移動(dòng)
h2開(kāi)始指向鏈表頭節(jié)點(diǎn)陕赃，若比較后是較小節(jié)點(diǎn)，則向后一節(jié)點(diǎn)移動(dòng)

方法二：直接求解基礎(chǔ)上采用遞歸方法

public class Solution {
    public Node<E> Merge(Node<E> h1,Node<E> h2) {
        // list1 list2為空的情況
        i(h1!=null || h2!=null){
            return h1 != null ? h1 : h2;
        }
        // 兩個(gè)鏈表元素依次對(duì)比
        if(h1.val <= h2.val){
            h1.next = Merge(h1.next, h2);
            return h1;
        }else{
            h2.next = Merge(h1, h2.next);
            return h2;
        } 
    }
}

解析：
根據(jù)返回結(jié)果逆推颁股，merge返回的是新的遞增鏈表么库，比較后的較小節(jié)點(diǎn)連接新的遞增鏈表，返回當(dāng)前較小節(jié)點(diǎn)

5甘有、合并K個(gè)已排序的鏈表
合并 k 個(gè)升序的鏈表并將結(jié)果作為一個(gè)升序的鏈表返回其頭節(jié)點(diǎn)

優(yōu)先隊(duì)列

public Node<E> mergeList(ArrayList<Node<E>> lists){
    if(lists==null||lists.size()==0){
        return null;
    }
    PriorityQueue queue=new PriorityQueue(lists.size(),comparator.omparingInt(o->o.val));
    //將各鏈表頭節(jié)點(diǎn)放入隊(duì)列
    for(Node<E> node:lists){
        queue.offer(node);
    }   
    Node<E> dummy=node(-1);
    Node<E> cur=dummy;
    while(queue.isEmpty()){
            //彈出最小節(jié)點(diǎn)
            Node<E> node=queue.poll();
            //新鏈表尾節(jié)點(diǎn)連接最小節(jié)點(diǎn)
            cur.next=node;
            //更新尾節(jié)點(diǎn)指針诉儒，重新指向尾節(jié)點(diǎn)
            cur=cur.next;
            將彈出節(jié)點(diǎn)的鏈表的下一個(gè)節(jié)點(diǎn)加入隊(duì)列
            if(node.next!=null){
                queue.offer(node.next);
            }
        }
    }
    return dummy;
}

6、判斷鏈表中是否有環(huán)
判斷給定的鏈表中是否有環(huán)亏掀。如果有環(huán)則返回true忱反，否則返回false

//速度必須設(shè)為1和2或1和2的倍數(shù),設(shè)為1和3可能不會(huì)相遇
public boolean hasCycle(Node head){
    //鏈表不存在或者只有一個(gè)節(jié)點(diǎn)的話都返回null
    if(head==null||head.next==null) return null;
    Node slow=head;
    //若一開(kāi)始指向同一位置泛释，則在開(kāi)始時(shí)就會(huì)相遇，后面做條件判斷會(huì)很麻煩
    Node fast=head.next;
    while(fast!=null&&fast.next!=null){
        //若存在環(huán)最終會(huì)相遇
        if(slow==fast) return true;
        slow=slow.next;
        fast=fast.next.next;            
    }
    return false;
}

解析：
需要用到兩個(gè)指針温算，相遇時(shí)指向同一節(jié)點(diǎn)
slow移動(dòng)速度為1
fast移動(dòng)速度為2

7怜校、鏈表中環(huán)的入口結(jié)點(diǎn)
給一個(gè)長(zhǎng)度為n鏈表，若其中包含環(huán)米者，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)韭畸，否則，返回null

方法一：hash法

public ListNode EntryNodeOfLoop(ListNode pHead) {
    // 使用set來(lái)記錄出現(xiàn)的結(jié)點(diǎn)
    HashSet<ListNode> set = new HashSet<>();
    while(pHead != null){
       // 當(dāng)set中包含結(jié)點(diǎn)蔓搞，說(shuō)明第一次出現(xiàn)重復(fù)的結(jié)點(diǎn)，即環(huán)的入口結(jié)點(diǎn)
        if(set.contains(pHead)){
            return pHead;
        }
        // set中加入未重復(fù)的結(jié)點(diǎn)
        set.add(pHead);
        pHead = pHead.next;
    }
    return null;
}

解析：
使用set或map集合存儲(chǔ)走過(guò)的節(jié)點(diǎn)随橘，當(dāng)下一次存進(jìn)來(lái)已經(jīng)保存過(guò)的節(jié)點(diǎn)時(shí)喂分，該節(jié)點(diǎn)即是入口節(jié)點(diǎn)

方法二：使用快慢指針

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode fast=pHead;
        ListNode slow=pHead;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)
                break;
        }
        if(fast==null||fast.next==null)
            return null;
   //   while(slow!=fast){
   //       if(fast==null||fast.next==null){
   //       return null;
   //       }
   //       slow=slow.next;
   //       fast=fast.next.next;
   //   }
        low=pHead;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

解析：
首先找到相遇節(jié)點(diǎn)，此時(shí)slow和fast都指向相遇節(jié)點(diǎn)
然后讓slow回到起點(diǎn)机蔗，此時(shí)fast未作變動(dòng)仍然指向相遇節(jié)點(diǎn)
使fast和low以相同速度出發(fā)蒲祈，根據(jù)推理fast和slow必定會(huì)在入口節(jié)點(diǎn)相遇，所以當(dāng)指向向同一節(jié)點(diǎn)時(shí)此節(jié)點(diǎn)即為入口節(jié)點(diǎn)

8萝嘁、鏈表中倒數(shù)最后k個(gè)結(jié)點(diǎn)
輸入一個(gè)長(zhǎng)度為 n 的鏈表梆掸，設(shè)鏈表中的元素的值為 ai ，返回該鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)牙言。
如果該鏈表長(zhǎng)度小于k酸钦，請(qǐng)返回一個(gè)長(zhǎng)度為 0 的鏈表

方法一：使用快慢指針

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode fast = pHead; 
        ListNode slow = pHead;
        //快指針先行k步
        for(int i = 0; i < k; i++){  
            if(fast != null)
                fast = fast.next;
            //達(dá)不到k步說(shuō)明鏈表過(guò)短，沒(méi)有倒數(shù)k
            else 
                return slow = null;
        }
        //快慢指針同步咱枉，快指針先到底卑硫，慢指針指向倒數(shù)第k個(gè)
        while(fast != null){ 
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

解析：
1、準(zhǔn)備慢指針指向原始鏈表頭
2蚕断、準(zhǔn)備一個(gè)快指針欢伏，從鏈表頭開(kāi)始，在鏈表上先走k步
3亿乳、快慢指針?lè)謩e從各自的當(dāng)前位置同步移動(dòng)硝拧，則他們距離始終保持為K，當(dāng)快指針到達(dá)尾部的時(shí)候葛假，慢指針正好到了倒數(shù)k個(gè)元素的位置

方法二：直接求解

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        int n = 0;
        ListNode p = pHead;
         //遍歷鏈表障陶，統(tǒng)計(jì)鏈表長(zhǎng)度
        while(p != null){
            n++;
            p = p.next;
        }
        //長(zhǎng)度過(guò)小，返回空鏈表
        if(n < k) 
            return null;
        p = pHead;
        //遍歷n-k次
        for(int i = 0; i < n - k; i++) 
            p = p.next;
        return p;
    }
}

解析：
1桐款、可以先遍歷一次鏈表找到鏈表的長(zhǎng)度咸这。
2、然后比較鏈表長(zhǎng)度是否比k小魔眨，如果比k小返回一個(gè)空節(jié)點(diǎn)媳维。
3酿雪、如果鏈表足夠長(zhǎng)，則我們從頭節(jié)點(diǎn)往后遍歷n?k次即可找到所求

9侄刽、刪除鏈表的倒數(shù)第n個(gè)節(jié)點(diǎn)

public Node removeNthTail(Node head,int n){
    //引入頭節(jié)點(diǎn):讓刪除head與其他情況一樣
    Node dummy=Node(-1);
    dummy.next=head;
    Node slow=dummy;
    Node fast=dummy;
    //fast移動(dòng)至待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)處
    while(n>-1){
        fast=fast.next;
        n--;
    }       
    while(fast!=null){
        fast=fast.next;
        slow=slow.next;
    }
    //此時(shí)fas指向null,slow指向待刪除節(jié)點(diǎn)前一個(gè)
    slow.next=slow.next.next;
    return dummy.next;
}

解析：
刪除倒數(shù)第n個(gè)節(jié)點(diǎn)指黎，需要slow指向倒數(shù)第n+1個(gè)節(jié)點(diǎn)
考慮到可能刪除頭節(jié)點(diǎn)，為使刪除頭節(jié)點(diǎn)和其他節(jié)點(diǎn)情況一致州丹，因此引入虛擬頭節(jié)點(diǎn)
slow指向虛擬頭節(jié)點(diǎn)
fast移動(dòng)n+1位
兩者同時(shí)移動(dòng)醋安，fast先到達(dá)末尾，當(dāng)fast指向null時(shí)則slow指向倒數(shù)n+1個(gè)節(jié)點(diǎn)

10墓毒、兩個(gè)鏈表中的第一個(gè)公共節(jié)點(diǎn)
輸入兩個(gè)無(wú)環(huán)的單向鏈表吓揪，找出它們的第一個(gè)公共結(jié)點(diǎn)，如果沒(méi)有公共節(jié)點(diǎn)則返回空

public Node<E> findFirstCommonNode(Node<E> h1,Node<> h2){
    Node<E> p1=h1;
    Node<E> p2=h2;
    while(p1==p2){
        p1=(p1.next==null?h2:p1.next);
        p2=(p2.next==null?h1:p2.next);
    }
    return p1;
}

解析：
由圖示分析可知當(dāng)所走路程相同時(shí)會(huì)相遇所计，p1柠辞、p2同時(shí)向后移動(dòng)一個(gè)節(jié)點(diǎn)，當(dāng)移動(dòng)至鏈表尾節(jié)點(diǎn)時(shí)主胧，分別從另一鏈表節(jié)點(diǎn)開(kāi)始移動(dòng)叭首，走到公共節(jié)點(diǎn)時(shí)所移動(dòng)路程剛好相同

11、單鏈表排序
給定一個(gè)節(jié)點(diǎn)數(shù)為n的無(wú)序單鏈表踪栋，對(duì)其按升序排序
方法一：使用數(shù)組

public class Solution {
 public ListNode sortInList (ListNode head) {
     if(head == null || head.next == null)
         return head;
     ArrayList<Integer> list = new ArrayList<>();
     ListNode tmp = head;
     while(tmp != null){
         list.add(tmp.val);
         tmp = tmp.next;
     }
     //數(shù)組遞增排序
     list.sort((a,b)->{return a-b;});
     ListNode temp = head;
     int i = 0;
     while(temp != null){
         //直接修改鏈表的值（此時(shí)數(shù)組中元素經(jīng)過(guò)之前的排序后是遞增的）
         temp.val = list.get(i++);
         temp = temp.next;
     }
     return head;
 }
}

解析：
將鏈表所有節(jié)點(diǎn)的值都放入數(shù)組中焙格，調(diào)用數(shù)組官方提供的排序方法將所有值排好序。再將數(shù)組中所有值取出賦值給鏈表

方法二：歸并（分治）

public Node listSort(Node head){
    if(head==null||head.next==null) return head;
    Node slow=head;
    Node fast=head.next;
    //快慢指針找到中點(diǎn)
    if(fast!=null || fast.next!=null){
        slow=slow.next;
        fast=fast.next.next;
    }
    //找到右半部分起始節(jié)點(diǎn)
    right=slow.next;
    //斷開(kāi)與右半部分的鏈接夷都，使其一分為二
    slow.next=null;
    
    left=listSort(head);
    right=listSort(right);

    //下面是合并部分
    Node tail=Node(-1);
    Node res=tail;

    while(left!=null&&right!=null){
        if(left.val<right.val){
            tail.next=left;
            left=left.next;
        }else{
            tail.next=right;
            right=right.next;
        }
        tail=tail.next;
    }
    tail.next=left.next==null?right:left;
    return res.next;
}

解析：
利用了歸并排序算法眷唉，歸并排序里面是數(shù)組可以直接利用索引，而鏈表需要利用指針

歸并排序：

void msort(int[] arr,int[] tempArr,int left,int right){
    // 0 1 2
    // (0,1) (2,2)X
    if(left<right){
        int mid=(left+right)/2; 
        //從上到下损肛，從左到右
        msort(arr,tempArr,left,mid);    (0,1)
        msort(arr,tempArr,mid+1,right);     (2,2)
        //從下到上厢破，從左到右
        merge(arr,tempArr,left,mid,right);      (0,1,2)
    }
}
void merge(int[] arr,int[] tempArr,int left,int mid,int right){
    //左邊數(shù)組起點(diǎn)下標(biāo)
    int lp=left;    
    //右邊數(shù)組起點(diǎn)下標(biāo)
    int rp=mid+1;
    //臨時(shí)數(shù)組下標(biāo)
    int pos=left;
    while(lp<=mid&&rp<=right){
        if(lp<=rp){
            tempArr[pos++]=arr[lp++];
        }else{
            tempArr[pos++]=arr[rp++];
        }
    }
    //合并過(guò)程中不斷排序，臨時(shí)數(shù)組會(huì)不斷重拍
    while(lp<=mid){
        temp[pos++]=arr[lp++];
    }
    while(rp<=right){
        temp[pos++]=arr[rp++];
    }
    //最后一次合并后排序的結(jié)果為最終結(jié)果
    while(left<=right){
        arr[left++]=tempArr[left++];
    }
}