2.链表（二）

题目汇总https://leetcode-cn.com/tag/linked-list/

92. 反转链表 II中等（看精选题解会清晰一点，自己还写不出来）

109. 有序链表转换二叉搜索树中等 [✔]

138. 复制带随机指针的链表(分三步走)

141. 环形链表简单[✔]

142. 环形链表 II中等[✔]

143. 重排链表中等[✔]

147. 对链表进行插入排序中等（看评论区好久才能大致理解）

148. 排序链表中等（递归解法不满足条件，需要迭代解法，存在问题）

160. 相交链表简单[✔]

203. 移除链表元素简单[✔]

92. 反转链表 II中等

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
类似题目206. 反转链表简单

思路：递归

递归反转整个链表的题理解了，但是这个题还是不会做。以下代码转自链接https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/bu-bu-chai-jie-ru-he-di-gui-di-fan-zhuan-lian-biao/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == 1) {
        // 相当于反转前 n 个元素
        return reverseN(head, n);
        }
        // 前进到反转的起点触发 base case
        head.next = reverseBetween(head.next, m - 1, n - 1);
        return head;
    }

    ListNode successor = null; // 后驱节点

    // 反转以 head 为起点的 n 个节点，返回新的头结点
    public ListNode reverseN(ListNode head, int n) {
        if (n == 1) { 
            // 记录第 n + 1 个节点
            successor = head.next;
            return head;
        }
        // 以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode last = reverseN(head.next, n - 1);

        head.next.next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head.next = successor;
        return last;
    }    

}

109. 有序链表转换二叉搜索树中等 [✔]

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

思路：递归

问题的关键是找到链表的中间元素，使用两个指针，慢指针每次向后移动一个节点，快指针每次移动两个节点。当快指针到链表的末尾时，慢指针正好访问到链表的中间元素，然后将链表从中间元素的左侧断开，递归调用即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {//执行用时 :1 ms, 在所有 Java 提交中击败了86.03%的用户,2020/08/05
        if(head == null)    
            return null;
        if(head.next == null)
            return new TreeNode(head.val);
        ListNode pre = head;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;//快指针每次走两步
            slow = slow.next;//慢指针每次走一步
        }
        while(pre.next != slow){
            pre = pre.next;
        }
        TreeNode root = new TreeNode(slow.val);//找到根节点
        ListNode hRight = slow.next;
        pre.next = null;//断开链表
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(hRight);
        return root;
    } 
}

138. 复制带随机指针的链表中等

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。

random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

思路：

本质和复制链表是一样的，只是这个链表的每个节点包含一个额外增加的随机指针random，先把复制的节点追加到每个节点之后，然后复制random指针，最后分割成两个链表，返回新复制的链表即可。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户，//2020/08/07
    public Node copyRandomList(Node head) {
        if(head == null)    return null;
        //1.复制每个节点，追加到原来的每个节点中
        Node cur = head;
        while(cur != null){
            Node copy = new Node(cur.val, cur.next, cur.random);
            copy.next = cur.next;
            cur.next = copy;
            cur = copy.next;
        }
        //2.复制random
        cur = head;
        while(cur != null){
            if(cur.random != null){
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        
        //3.分割原链表和复制的链表
        Node node = head;
        Node newHead = head.next;
        Node newNode = newHead;
        while(node != null){
            node.next = node.next.next;
            if(newNode.next != null){
                newNode.next = newNode.next.next;
            }
            node = node.next;
            newNode = newNode.next;
        }
    return newHead;
    }
}

141. 环形链表简单[✔]

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

思路：双指针

定义两个指针，一快一慢，快指针每次走两步，慢指针每次走一步。如果链表中不存在环，最终快指针将会最先到达尾部，此时返回 false。如果链表中存在环，那么快指针最终一定会追上慢指针。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户,2020/08/05
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null)   return false;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow)    return true;//快慢指针相遇，一定存在环
        }
    return !(fast == null || fast.next == null);
    }
}

142. 环形链表 II中等[✔]

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

思路：双指针

与上一题相比，情况复杂一些，不仅判断是否有环，还要找到环的入口节点。
在链表头与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户，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. 重排链表中等[✔]

给定一个单链表 L：L₀→L₁→…→L_n-1→L_{n ，}
将其重新排列后变为： L₀→L_n→L₁→L_n-1→L₂→L_n-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.
 * 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 {//执行用时：3 ms, 在所有 Java 提交中击败了37.99%的用户，//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.至此，分割成两个链表
        ListNode right = reverse(newHead);//2.反转右半部分链表
       
        while (right != null) { //3.依次连接两个链表节点
            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. 对链表进行插入排序中等

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
示例：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。

每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。

重复直到所有输入数据插入完为止。

思路：

引用评论区

/**
 * 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) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路一：递归，不满足常数级空间复杂度

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 //递归做法，不满足常数级空间复杂度
class Solution {//执行用时：3 ms, 在所有 Java 提交中击败了99.16%的用户，//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);
    }


    //合并两个有序链表
     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 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        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. 相交链表简单[✔]

编写一个程序，找到两个单链表相交的起始节点。

思路一：

如果两个链表相交，那么他们一定有相同的尾结点，分别遍历两个链表，记录他们的尾结点，如果他们的尾结点相同，那么这两个表相交。分别计算两个链表的长度，先对链表head1遍历(len1-len2)(假设len1>len2)个结点到结点p，此时结点p与head2到他们相交的结点的距离相等。此时同时遍历两个链表，直到遇到相同的结点为止，这个结点就是交点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户，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的长度
        }

        int lenB = 1;
        ListNode tailB = headB;
        while(tailB.next != null){
            tailB = tailB.next;
            lenB++;//链表B的长度
        }

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

思路二：

也是为了消除长度差，但是代码更简洁
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 继续遍历
如果 pB 到了末尾，则 pB = headA 继续遍历
比较长的链表指针指向较短链表head时，长度差就消除了
如此，只需要将最短链表遍历两次即可找到位置

/**
 * 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. 移除链表元素简单[✔]

删除链表中等于给定值 val 的所有节点。
示例:
输入: 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 {//执行用时：1 ms, 在所有 Java 提交中击败了99.72%的用户，//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;
    }
}