1、翻转链表
方法一：使用栈

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;
}

解析：
先将链表的所有节点放入栈中，弹出第一个节点作为新的头节点，将弹出的剩下节点依次接到后面（第三个while循环临时节点tempNode和当前节点node交替赋值，直到取出栈中所有节点）node.next=tempNode将取出的临时节点依次挂载到当前节点的后面，当取出栈中最后一个节点时需要断掉依赖（否则会形成双链）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;
}

解析：
其实就是将原链表的节点依次摘掉，形成一条新链表。每次摘掉的节点作为新链表的头节点（摘掉的节点接到新链表的前面），临时节点temp和当前节点head交替赋值就能取出全部节点，head.next=newhead将每次取出的当前节点接在新链表最前面，newHead=head 更新新链表头节点

两种方法的区别：
栈解决 在放入栈中再取出节点这个过程中重新取出的节点 顺序实际已经被倒置 所以只需要按照链表添加方法那样依次将取出节点接到后面即可
双链表解决 将原链表节点依次摘掉，摘掉的节点依次接到新链表前面

方法三：使用递归

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)进行递归调用，一直取到链表最后一个节点时跳出递归，返回的是原链表最后一个节点，用来作为新链表的头节点newHead，每次递归结束的返回值都是newHead。head.next.next=head每次取出的当前节点的下一个节点指向当前节点，head.next=null每次取出的当前节点的下一个节点变为null

2、翻转部分链表
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 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指向修改区域前一个节点
        pre=preHead.next;
    }
    //保存前继节点
    Node<E> preHead=pre;
    //翻转链表的头节点
    Node<E> cur=preHead.next;
    int i=0;
    //while(m<=n)
    while(i<n-m+1){  
        //保留下一个节点
        Node<E> temp=cur.next;
        //原链表摘掉的节点连接新链表头节点
        cur.next=pre;
        //更新新链表头节点
        pre=cur;
        //更新原链表下次需要摘掉的节点
        cur=temp;
        i++;
    }
    //链接后面
    preHead.next.next=cur;  
    //链接前面
    prehead.next=pre;  
    return newHead.next;
}

解析：
先找到需要翻转区域的前一个节点pre作为新链表的头节点preHead,然后按照双链表翻转的思路求解，最后需要处理好翻转完成后首尾节点的链接

3、链表中的节点每K个一组翻转
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样

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;

    //前继节点
    Node<E> prev=dummy;
    Node<E> start=dummy.next;
    Node<E> end=dummy.next;
    while(pre!=null){
        //找到本组最后一个节点
        for(int i=0;i<k-1&&end!=null;i++) end=end.next;
        //不足一组，直接返回结果
        if(end==null) break;
        //缓存本组后继节点
        Node<E> follow=end.next;
        //断掉下一组的连接
        end.next=null;
        //反转后start指针指向本组最后一个节点,end指针指向头节点
        //reverse返回新链表头节点
        prev.next=reverse(start);
        //重新连接
        start.next=follow;
        //更新前继节点
        prev=start;
    }
}
public static Node<E> reverse(Node<E> head){
    Node<E> cur=head;
    Node<E> newHead=null;
    while(head.next!=null){
        //缓存下一个节点
        Noede<E> temp=cur.next;
        //摘掉原链表的节点连接到新链表的最前面作为头节点
        cur.next=newHead;
        //更新新链表
        newHead=cur;
        //更新原链表头节点
        cur=temp;
    }
    return newHead;
}

解析：
需要用到四个指针
prev前继节点 指向每K组节点链表的前一个节点
follow后继节点 指向每K组节点链表的后一个节点
start开始节点：翻转前指向头节点，翻转后头节点变为尾节点，start随即改变指向为尾节点，此时利用start链接后继节点，利用start更新前继节点
end结束节点：翻转前指向尾节点，利用其断掉下一组的连接，翻转后随即指向开始节点

4、合并两个排序的链表
输入两个递增的链表，单个链表的长度为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;
        }
        //更新新链表尾节点
        cur=cur.next;
    }
    //新链表尾节点连接没有比较完的链表
    cur.next=(h1==null?h2:h1);
    return dummy;
}

解析：
合并递增判断出需要节点间比较，让指针不断移动指向每次比较后的新节点，再连接成串形成新链表
需要用到三个指针
cur开始指向虚拟节点，指向每次比较结果节点值小的节点
h1开始指向链表头节点，若比较后是较小节点，则向后一节点移动
h2开始指向链表头节点，若比较后是较小节点，则向后一节点移动

方法二：直接求解基础上采用递归方法

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;
        }
        // 两个链表元素依次对比
        if(h1.val <= h2.val){
            h1.next = Merge(h1.next, h2);
            return h1;
        }else{
            h2.next = Merge(h1, h2.next);
            return h2;
        } 
    }
}

解析：
根据返回结果逆推，merge返回的是新的递增链表，比较后的较小节点连接新的递增链表，返回当前较小节点

5、合并K个已排序的链表
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点

优先队列

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));
    //将各链表头节点放入队列
    for(Node<E> node:lists){
        queue.offer(node);
    }   
    Node<E> dummy=node(-1);
    Node<E> cur=dummy;
    while(queue.isEmpty()){
            //弹出最小节点
            Node<E> node=queue.poll();
            //新链表尾节点连接最小节点
            cur.next=node;
            //更新尾节点指针，重新指向尾节点
            cur=cur.next;
            将弹出节点的链表的下一个节点加入队列
            if(node.next!=null){
                queue.offer(node.next);
            }
        }
    }
    return dummy;
}

6、判断链表中是否有环
判断给定的链表中是否有环。如果有环则返回true，否则返回false

//速度必须设为1和2或1和2的倍数,设为1和3可能不会相遇
public boolean hasCycle(Node head){
    //链表不存在或者只有一个节点的话都返回null
    if(head==null||head.next==null) return null;
    Node slow=head;
    //若一开始指向同一位置，则在开始时就会相遇，后面做条件判断会很麻烦
    Node fast=head.next;
    while(fast!=null&&fast.next!=null){
        //若存在环最终会相遇
        if(slow==fast) return true;
        slow=slow.next;
        fast=fast.next.next;            
    }
    return false;
}

解析：
需要用到两个指针，相遇时指向同一节点
slow移动速度为1
fast移动速度为2

7、链表中环的入口结点
给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null

方法一：hash法

public ListNode EntryNodeOfLoop(ListNode pHead) {
    // 使用set来记录出现的结点
    HashSet<ListNode> set = new HashSet<>();
    while(pHead != null){
       // 当set中包含结点，说明第一次出现重复的结点，即环的入口结点
        if(set.contains(pHead)){
            return pHead;
        }
        // set中加入未重复的结点
        set.add(pHead);
        pHead = pHead.next;
    }
    return null;
}

解析：
使用set或map集合存储走过的节点，当下一次存进来已经保存过的节点时，该节点即是入口节点

方法二：使用快慢指针

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;
    }
}

解析：
首先找到相遇节点，此时slow和fast都指向相遇节点
然后让slow回到起点，此时fast未作变动仍然指向相遇节点
使fast和low以相同速度出发，根据推理fast和slow必定会在入口节点相遇，所以当指向向同一节点时此节点即为入口节点

8、链表中倒数最后k个结点
输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 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;
            //达不到k步说明链表过短，没有倒数k
            else 
                return slow = null;
        }
        //快慢指针同步，快指针先到底，慢指针指向倒数第k个
        while(fast != null){ 
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

解析：
1、准备慢指针指向原始链表头
2、准备一个快指针，从链表头开始，在链表上先走k步
3、快慢指针分别从各自的当前位置同步移动，则他们距离始终保持为K，当快指针到达尾部的时候，慢指针正好到了倒数k个元素的位置

方法二：直接求解

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        int n = 0;
        ListNode p = pHead;
         //遍历链表，统计链表长度
        while(p != null){
            n++;
            p = p.next;
        }
        //长度过小，返回空链表
        if(n < k) 
            return null;
        p = pHead;
        //遍历n-k次
        for(int i = 0; i < n - k; i++) 
            p = p.next;
        return p;
    }
}

解析：
1、可以先遍历一次链表找到链表的长度。
2、然后比较链表长度是否比k小，如果比k小返回一个空节点。
3、如果链表足够长，则我们从头节点往后遍历n−k次即可找到所求

9、删除链表的倒数第n个节点

public Node removeNthTail(Node head,int n){
    //引入头节点:让删除head与其他情况一样
    Node dummy=Node(-1);
    dummy.next=head;
    Node slow=dummy;
    Node fast=dummy;
    //fast移动至待删除节点的前一个节点处
    while(n>-1){
        fast=fast.next;
        n--;
    }       
    while(fast!=null){
        fast=fast.next;
        slow=slow.next;
    }
    //此时fas指向null,slow指向待删除节点前一个
    slow.next=slow.next.next;
    return dummy.next;
}

解析：
删除倒数第n个节点，需要slow指向倒数第n+1个节点
考虑到可能删除头节点，为使删除头节点和其他节点情况一致，因此引入虚拟头节点
slow指向虚拟头节点
fast移动n+1位
两者同时移动，fast先到达末尾，当fast指向null时则slow指向倒数n+1个节点

10、两个链表中的第一个公共节点
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空

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;
}

解析：
由图示分析可知当所走路程相同时会相遇，p1、p2同时向后移动一个节点，当移动至链表尾节点时，分别从另一链表节点开始移动，走到公共节点时所移动路程刚好相同

11、单链表排序
给定一个节点数为n的无序单链表，对其按升序排序
方法一：使用数组

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;
     }
     //数组递增排序
     list.sort((a,b)->{return a-b;});
     ListNode temp = head;
     int i = 0;
     while(temp != null){
         //直接修改链表的值（此时数组中元素经过之前的排序后是递增的）
         temp.val = list.get(i++);
         temp = temp.next;
     }
     return head;
 }
}

解析：
将链表所有节点的值都放入数组中，调用数组官方提供的排序方法将所有值排好序。再将数组中所有值取出赋值给链表

方法二：归并（分治）

public Node listSort(Node head){
    if(head==null||head.next==null) return head;
    Node slow=head;
    Node fast=head.next;
    //快慢指针找到中点
    if(fast!=null || fast.next!=null){
        slow=slow.next;
        fast=fast.next.next;
    }
    //找到右半部分起始节点
    right=slow.next;
    //断开与右半部分的链接，使其一分为二
    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;
}

解析：
利用了归并排序算法，归并排序里面是数组可以直接利用索引，而链表需要利用指针

归并排序：

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){
    //左边数组起点下标
    int lp=left;    
    //右边数组起点下标
    int rp=mid+1;
    //临时数组下标
    int pos=left;
    while(lp<=mid&&rp<=right){
        if(lp<=rp){
            tempArr[pos++]=arr[lp++];
        }else{
            tempArr[pos++]=arr[rp++];
        }
    }
    //合并过程中不断排序，临时数组会不断重拍
    while(lp<=mid){
        temp[pos++]=arr[lp++];
    }
    while(rp<=right){
        temp[pos++]=arr[rp++];
    }
    //最后一次合并后排序的结果为最终结果
    while(left<=right){
        arr[left++]=tempArr[left++];
    }
}