思路：雙指針

與上一題相比，情況復(fù)雜一些，不僅判斷是否有環(huán)，還要找到環(huán)的入口節(jié)點(diǎn)。
在鏈表頭與相遇點(diǎn)分別設(shè)一個(gè)指針，每次各走一步，兩個(gè)指針必定相遇，且相遇第一點(diǎn)為環(huán)入口點(diǎn)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {//執(zhí)行用時(shí) :0 ms, 在所有 Java 提交中擊敗了100.00%的用戶(hù)，2020/08/05
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        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;
        slow = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
    return slow; 
    }
}

143. 重排鏈表中等[?]

給定一個(gè)單鏈表 L：L₀→L₁→…→L_n-1→L_{n ，}
將其重新排列后變?yōu)椋?L₀→L_n→L₁→L_n-1→L₂→L_n-2→…
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。
示例 1:
給定鏈表 1->2->3->4, 重新排列為 1->4->2->3.
示例 2:
給定鏈表 1->2->3->4->5, 重新排列為 1->5->2->4->3.

思路：

將鏈表平均分成兩半，將第二個(gè)鏈表逆序，依次連接兩個(gè)鏈表。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {//執(zhí)行用時(shí)：3 ms, 在所有 Java 提交中擊敗了37.99%的用戶(hù)，//2020/08/05
    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.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 newHead = slow.next;
        slow.next = null;//1.至此，分割成兩個(gè)鏈表
        ListNode right = reverse(newHead);//2.反轉(zhuǎn)右半部分鏈表
       
        while (right != null) { //3.依次連接兩個(gè)鏈表節(jié)點(diǎn)
            ListNode temp = right.next;
            right.next = head.next;
            head.next = right;
            head = right.next;
            right = temp;
        }
    }

    public ListNode reverse(ListNode head){
        if(head == null || head.next == null)   return head;
        ListNode cur = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }
}

147. 對(duì)鏈表進(jìn)行插入排序中等

對(duì)鏈表進(jìn)行插入排序。

插入排序的動(dòng)畫(huà)演示如上。從第一個(gè)元素開(kāi)始，該鏈表可以被認(rèn)為已經(jīng)部分排序（用黑色表示）。每次迭代時(shí)，從輸入數(shù)據(jù)中移除一個(gè)元素（用紅色表示），并原地將其插入到已排好序的鏈表中。
示例 ：
輸入: -1->5->3->4->0
輸出: -1->0->3->4->5
插入排序算法：

1. 插入排序是迭代的，每次只移動(dòng)一個(gè)元素，直到所有元素可以形成一個(gè)有序的輸出列表。
2. 每次迭代中，插入排序只從輸入數(shù)據(jù)中移除一個(gè)待排序的元素，找到它在序列中適當(dāng)?shù)奈恢?，并將其插入?/li>
3. 重復(fù)直到所有輸入數(shù)據(jù)插入完為止。

思路：

引用評(píng)論區(qū)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null)  return head;
        ListNode dummy = new ListNode(-1);//偽頭指針
        dummy.next = head;
        ListNode pre = head;

        while (head != null && head.next != null)
        {
            if(head.val <= head.next.val) {
                head = head.next;
                continue;
            }
            pre = dummy;
            
            while (pre.next.val < head.next.val) pre = pre.next;
            
            ListNode curr = head.next;
            head.next = curr.next;
            curr.next = pre.next;
            pre.next = curr;
        }
        return dummy.next;

    }
}

148. 排序鏈表中等

在 O(n log n) 時(shí)間復(fù)雜度和常數(shù)級(jí)空間復(fù)雜度下，對(duì)鏈表進(jìn)行排序。
示例 1:
輸入: 4->2->1->3
輸出: 1->2->3->4
示例 2:
輸入: -1->5->3->4->0
輸出: -1->0->3->4->5

思路一：遞歸，不滿(mǎn)足常數(shù)級(jí)空間復(fù)雜度

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 //遞歸做法，不滿(mǎn)足常數(shù)級(jí)空間復(fù)雜度
class Solution {//執(zhí)行用時(shí)：3 ms, 在所有 Java 提交中擊敗了99.16%的用戶(hù)，//2020/08/05
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null)    return head;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode midNode = slow;
        ListNode rightNode = midNode.next;
        midNode.next = null;

        ListNode left = sortList(head);//排序左半部分鏈表
        ListNode right = sortList(rightNode);//排序右半部分鏈表
        return mergeTwoLists(left, right);
    }


    //合并兩個(gè)有序鏈表
     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       ListNode dummy = new ListNode(-1);
       ListNode cur = dummy;
       while(l1 != null && l2 != null){
           if(l1.val <= l2.val){
               cur.next = l1;
               l1 = l1.next;
           }else{
               cur.next = l2;
               l2 = l2.next;
           }
           cur = cur.next;
       }
        // 合并后 l1 和 l2 最多只有一個(gè)還未被合并完，我們直接將鏈表末尾指向未合并完的鏈表即可
        cur.next = l1 == null ? l2 : l1;

    return dummy.next;
    }
}

思路二：迭代（看不懂）

https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/

160. 相交鏈表簡(jiǎn)單[?]

編寫(xiě)一個(gè)程序，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。

思路一：

如果兩個(gè)鏈表相交，那么他們一定有相同的尾結(jié)點(diǎn)，分別遍歷兩個(gè)鏈表，記錄他們的尾結(jié)點(diǎn)，如果他們的尾結(jié)點(diǎn)相同，那么這兩個(gè)表相交。分別計(jì)算兩個(gè)鏈表的長(zhǎng)度，先對(duì)鏈表head1遍歷(len1-len2)(假設(shè)len1>len2)個(gè)結(jié)點(diǎn)到結(jié)點(diǎn)p，此時(shí)結(jié)點(diǎn)p與head2到他們相交的結(jié)點(diǎn)的距離相等。此時(shí)同時(shí)遍歷兩個(gè)鏈表，直到遇到相同的結(jié)點(diǎn)為止，這個(gè)結(jié)點(diǎn)就是交點(diǎn)。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {//執(zhí)行用時(shí)：1 ms, 在所有 Java 提交中擊敗了100.00%的用戶(hù)，2020/08/01
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)  return null;
        int lenA = 1;
        ListNode tailA = headA;
        while(tailA.next != null){
            tailA = tailA.next;
            lenA++;//鏈表A的長(zhǎng)度
        }

        int lenB = 1;
        ListNode tailB = headB;
        while(tailB.next != null){
            tailB = tailB.next;
            lenB++;//鏈表B的長(zhǎng)度
        }

        if(tailA != tailB)  return null;
        ListNode nodeA = headA;
        ListNode nodeB = headB;
        if(lenA > lenB){
            int d = lenA - lenB;
            while(d != 0){
                nodeA = nodeA.next;
                d--;
            }
        }else{
            int d = lenB - lenA;
            while(d != 0){
                nodeB = nodeB.next;
                d--;
            }
        }
        while(nodeA != nodeB){
            nodeA = nodeA.next;
            nodeB = nodeB.next;
        }
        return nodeA;
    }
}

思路二：

也是為了消除長(zhǎng)度差，但是代碼更簡(jiǎn)潔
https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/tu-jie-xiang-jiao-lian-biao-by-user7208t/
指針 pA 指向 A 鏈表，指針 pB 指向 B 鏈表，依次往后遍歷
如果 pA 到了末尾，則 pA = headB 繼續(xù)遍歷
如果 pB 到了末尾，則 pB = headA 繼續(xù)遍歷
比較長(zhǎng)的鏈表指針指向較短鏈表head時(shí)，長(zhǎng)度差就消除了
如此，只需要將最短鏈表遍歷兩次即可找到位置

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

203. 移除鏈表元素簡(jiǎn)單[?]

刪除鏈表中等于給定值 val 的所有節(jié)點(diǎn)。
示例:
輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5

思路：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {//執(zhí)行用時(shí)：1 ms, 在所有 Java 提交中擊敗了99.72%的用戶(hù)，//2020/08/05
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while(cur != null){
            if(cur.val == val){
                pre.next = cur.next;
            }else{
                pre = cur;
            }
            cur = cur.next;
        }
    return dummy.next;
    }
}