判断链表是否有环

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

快慢指针

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow==fast){
                return true;
            }
        }
        return false;
    }
}

判断入环点是哪一个节点

有S2=2*S1。 S1= sp, S2=sp+pp(fast绕了一圈)
所以有sp=pp，sp=se+ep,pp = pe+ep,所以se = pe这个等式很关键

public class Solution {
    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){
                fast = head;
                while(fast!=slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int a = 0;
        int b = 0;
        ListNode a1 = headA;
        ListNode b1 = headB;
        while (a1 != null) {
            a++;
            a1 = a1.next;
        }
        while (b1 != null) {
            b++;
            b1 = b1.next;
        }
        while (a > b) {
            a--;
            headA = headA.next;
        }
        while (a < b) {
            b--;
            headB = headB.next;
        }
        while ((headA != null) && (headB != null)) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}

方法2
public class Solution {
   public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    /**
     定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
     两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
     **/
    if(headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
    while(pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}
}

反转链表

重点就是
ListNode pre = null; 开始指向虚空null

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }
        return pre;
    }
}

是否为回文链表

O(1) 空间复杂度
快慢指针找到中间节点，然后把后半段链表反转

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while ((fast != null) && (fast.next != null)) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode pre = null;
        ListNode cur = slow;

        while (cur != null) {
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }

        cur = head;

        while ((pre != null) && (cur != null)) {
            if (cur.val != pre.val) {
                return false;
            }

            pre = pre.next;
            cur = cur.next;
        }

        return true;
    }
}

旋转链表

你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

先将给定的链表连接成环，然后将指定位置断开
怎么找到断开的点，也就是新链表的最后一个节点：sum-k%sum

注意sum从1开始，当head为null时提前返回

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null){
            return null;
        }
        int sum = 1;
        ListNode end = head;
        while(end.next!=null){
            sum++;
            end = end.next;
        }
        end.next = head;
        int t = sum-k%sum;
        while(t>0){
            end = end.next;
            t--;    
        }
        ListNode r = end.next;
        end.next=null;
        return r;
    }
}

对链表升序排序

O(n log n) 时间复杂度和常数级空间复杂度下

关键点时令一个新的头节点和一个结果节点指向头节点。

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        //找中点
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //偶数时左边的节点
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode pre = new ListNode();
        ListNode r = pre;
        while(left!=null&&right!=null){
            if(left.val<right.val){
                pre.next = left;
                left = left.next;
            }else{
                pre.next = right;
                right = right.next;
            }
            pre = pre.next;
        }
        if(left!=null){
            pre.next = left;
        }else if(right!=null){
            pre.next = right;
        }
        return r.next;

    }
}

分割链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。

此题其实就是将原链表分成两个小链表，其中一个的节点值小于x，另一个的节点值大于等于x，然后再将这两个链表合并即可。

注意：虚拟头节点的使用，虚拟头节点可以避免一些边界情况的处理，最后返回时只需要返回list.next即可
注意：要记得断开原链表的next指针

class Solution {
    public ListNode partition(ListNode head, int x) {
         // 比x小的节点的数组
        ListNode list1 = new ListNode(0);
        // 比x>=的节点的数组
        ListNode list2 = new ListNode(0);
        ListNode a1 = list1;
        ListNode a2 = list2;
       ListNode p = head;
       while(p!=null){
           if(p.val<x){
            a1.next = p;
            a1 = a1.next;
           }else{
            a2.next = p;
            a2 = a2.next;
           }
           ListNode t = p.next;
           p.next = null;
           p=t;
       }
        a1.next = list2.next;
        return list1.next;
    }
}

重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

有额外存储空间解法
把链表存储到线性表中，然后用双指针依次从头尾取元素即可

class Solution {
    public void reorderList(ListNode head) {
        if(head==null){
            return;
        }
        List<ListNode> list = new ArrayList<>();
        ListNode end = head;
        while(end.next!=null){
            list.add(end);
            end = end.next;
        }
        list.add(end);
        int i = 0;
        int j = list.size()-1;
        while(i<j){
            list.get(i).next = list.get(j);
            i++;
            if(i==j){
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }
}

方法2
反转后面一半的链表

1 -> 2 -> 3 -> 4 -> 5 -> 6
第一步，将链表平均分成两半
1 -> 2 -> 3
4 -> 5 -> 6
    
第二步，将第二个链表逆序
1 -> 2 -> 3
6 -> 5 -> 4
    
第三步，依次连接两个链表
1 -> 6 -> 2 -> 5 -> 3 -> 4

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode mid = middleNode(head);
        ListNode l1 = head;
        ListNode l2 = mid.next;
        mid.next = null;
        l2 = reverseList(l2);
        mergeList(l1, l2);
    }

    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    public void mergeList(ListNode l1, ListNode l2) {
        ListNode l1_tmp;
        ListNode l2_tmp;
        while (l1 != null && l2 != null) {
            l1_tmp = l1.next;
            l2_tmp = l2.next;

            l1.next = l2;
            l1 = l1_tmp;

            l2.next = l1;
            l2 = l2_tmp;
        }
    }
}