1. 重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

解法：

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    public void reorderList(ListNode head) {
        if(head==null || head.next==null){
            return;
        }
        //快慢指针找中间结点
        ListNode slow=head;
        ListNode fast=head;
        while(fast.next!=null && fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        //拆分链表
        ListNode after=slow.next;
        slow.next=null;
        //反转后半部分链表
        ListNode pre=null;
        while(after!=null){
            ListNode temp=after.next;
            after.next=pre;
            pre=after;
            after=temp;
        }
        //合并两个链表
        ListNode p1=head;
        ListNode p2=pre;
        while(p1!=null && p2!=null){
            ListNode p1temp=p1.next;
            ListNode p2temp=p2.next;
            p1.next=p2;
            p2.next=p1temp;
            p1=p1temp;
            p2=p2temp;
        }
        return;
    }
}

2. 链表中的环入口结点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解法：

1. 第一步，找环中相汇点。分别用slow，fast指向链表头部，slow每次走一步，fast每次走二步，直到slow==fast找到在环中的相汇点。
2. 第二步，找环的入口。接上步，当fast==slow时，fast所经过节点数为2x,slow所经过节点数为x,设环中有n个节点,fast比slow多走k圈有2x=nk+x; x=nk;可以看出slow实际走了k个环的步数，再让fast指向链表头部，slow位置不变，slow,fast每次走一步直到fast == slow ，此时slow指向环的入口。

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null || head.next==null){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast.next!=null && fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                fast=head;
                while(fast!=slow){
                    slow=slow.next;
                    fast=fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

3. 复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。

解法：

1. 复制每个节点，如：复制节点A得到A1，将A1插入节点A后面
2. 遍历链表，A1->random = A->random->next
3. 将链表拆分成原链表和复制后的链表

/** * Definition for singly-linked list with a random pointer. * class RandomListNode { * int label; * RandomListNode next, random; * RandomListNode(int x) { this.label = x; } * }; */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head==null){
            return null;
        }
        //复制链表
        RandomListNode current=head;
        while(current!=null){
            RandomListNode temp=current.next;
            RandomListNode copy=new RandomListNode(current.label);
            current.next=copy;
            copy.next=temp;
            
            current=temp;
        }
        //2.
        current=head;
        while(current!=null){
            RandomListNode copy=current.next;
            if(current.random!=null){
                copy.random=current.random.next;
            }else{
                copy.random=null;
            }
            
            current=copy.next;
        }
        //拆分
        RandomListNode copyHead=head.next;
        current=head;
        while(current.next!=null){
            RandomListNode temp=current.next;
            current.next=temp.next;
            current=temp;
        }
        return copyHead;
    }
}

4. 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

解法：
链表查找中间点可以通过快慢指针来操作。找到中点后，要以中点的值建立一个树的根节点，然后需要把原链表断开，分为前后两个链表，都不能包含原中节点，然后再分别对这两个链表递归调用原函数，分别连上左右子节点即可。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; next = null; } * } */
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return toBST(head, null);
    }
    
    private TreeNode toBST(ListNode head, ListNode tail) {
        if (head == tail){
            return null;
        }
        //找中间节点
        ListNode fast = head;
        ListNode slow = head;
        while (fast != tail && fast.next != tail) {
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = toBST(head, slow);
        root.right = toBST(slow.next, tail);
        return root;
    }
}

5. 反转从位置m到n的链表

请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

解法：
不妨拿出四本书，摞成一摞（自上而下为 A B C D），要让这四本书的位置完全颠倒过来（即自上而下为 D C B A）：
盯住书A，每次操作把A下面的那本书放到最上面
初始位置：自上而下为 A B C D
第一次操作后：自上而下为 B A C D
第二次操作后：自上而下为 C B A D
第三次操作后：自上而下为 D C B A

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        //建一个辅助节点，处理m=1的情况
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode preStart = dummy;
        ListNode start = head;
        for (int i = 1; i < m; i ++ ) {
            preStart = start;
            start = start.next;
        }
        // reverse
        for (int i = 0; i < n - m; i ++ ) {
            ListNode temp = start.next;
            start.next = temp.next;
            temp.next =preStart.next;
            preStart.next = temp;
        }
        return dummy.next;
    }
}

6. 删除排序链表中的重复元素

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。
示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:

输入: 1->1->1->2->3
输出: 2->3

解法：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode dummy=new ListNode(head.val-1);//避免与头结点相同
        dummy.next=head;
        
        ListNode pre=dummy;
        ListNode after=head;
        
        while(after!=null && after.next!=null){
            if(after.val!=after.next.val){
                pre=after;
                after=after.next;
            }else{
                while(after.next!=null && after.next.val==after.val){
                    after=after.next;
                }
                pre.next=after.next;
                after=after.next;
            }
        }
        return dummy.next;
    }
}

7. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

解法：
先遍历一遍，得出链表长度count，注意k可能会大于count，因此k%=count。
将尾结点next指针指向首节点，形成一个环，从尾节点向后跑count-k步，从这里断开，就是结果。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if(head==null || n==0){
            return head;
        }
        ListNode p=head;
        int count=1;
        while(p.next!=null){
            count++;
            p=p.next;
        }
        //首尾相连
        p.next=head;
        int step=count-n%count;
        //从尾节点开始走
        for(int i=0;i<step;i++){
            p=p.next;
        }
        ListNode newHead=p.next;
        //断开环
        p.next=null;
        return newHead;
    }
}

8. k个一组翻转链表

给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。

示例 :

给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

解法：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null){
            return head;
        }
        //求链表长度
        int len=0;
        ListNode p=head;
        while(p!=null){
            len++;
            p=p.next;
        }
        
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        
        ListNode pre=dummy,cur=head,temp;
        for(int i=0;i<len/k;i++){
            //翻转，每次将当前节点的下一节点提到最前面
            for(int j=1;j<k;j++){
                temp=cur.next;
                cur.next=temp.next;
                temp.next=pre.next;
                pre.next=temp;
            }
            pre=cur;
            cur=cur.next;
        }
        return dummy.next;
    }
}

9. 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：给定的 n 保证是有效的。尝试使用一趟扫描实现。

解法：采用两个指针，对前指针，使其先走出N步，随后两个指针同时前进，当前指针到达链表尾部时，后指针到达倒数第N个节点的位置。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null){
            return head;
        }
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        
        ListNode pre=dummy,after=head;
        for(int i=1;i<n;i++){
            after=after.next;
        }
        //after到达尾节点时，pre指向要删除节点的前一个节点
        while(after.next!=null){
            pre=pre.next;
            after=after.next;
        }
        pre.next=pre.next.next;
        return dummy.next;
    }
}