LeetCode链表

//比较推荐的写法，简洁一点，在 lc 上提交区别不大
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyNode=new ListNode(-1);
    ListNode temp=dummyNode;
    dummyNode.next=temp;
    int carry=0;
    while(l1!=null || l2!=null){
        int sum= (l1!=null?l1.val:0) + (l2!=null?l2.val:0)+ carry;
        temp.next=new ListNode(sum%10);
        temp=temp.next;
        carry=sum/10;
        l1=l1!=null?l1.next:null;
        l2=l2!=null?l2.next:null;
    }
    if(carry!=0) temp.next=new ListNode(1);
    return dummyNode.next;
}

//这个解法有点偏了，为了不 new 节点直接在原链表上修改的
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyNode=new ListNode(-1);
    dummyNode.next=l1;
    int carry=0;
    ListNode last=l1;
    while(l1!=null && l2!=null){
        int sum= l1.val + l2.val+ carry;
        l1.val=sum%10;
        carry=sum/10;
        last=l1;
        l1=l1.next;
        l2=l2.next;
    }
    while(l1!=null && carry!=0){
        int sum = l1.val + carry;
        l1.val=sum%10;
        carry=sum/10;
        last=l1;
        l1=l1.next;
    }
    if(l2!=null){
        last.next=l2;
        while(l2!=null && carry!=0){
            int sum = l2.val + carry;
            l2.val=sum%10;
            carry=sum/10;
            last=l2;
            l2=l2.next;
        }
    }
    if(carry!=0) last.next=new ListNode(1);
    return dummyNode.next;
}

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    BigInteger b1 = new BigInteger(list2num(l1));
    BigInteger b2 = new BigInteger(list2num(l2));
    String resStr=b1.add(b2).toString();
    //再变成字符串存到连表里面
    ListNode res=new ListNode(1);
    ListNode real=res;
    for (int i=0;i<resStr.length();i++) {
        real.next=new ListNode(Integer.valueOf(resStr.charAt(i)-48));
        real=real.next;
    }
    return res.next;
}
public static String  list2num(ListNode l){
    String num="";
    while(l!=null){
        num=num+l.val;
        l=l.next;
    }
    return num;
}

public  ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    //用数组的话不知道有多长，需要多遍历两遍
    Deque<Integer> stack1=new ArrayDeque<>();
    Deque<Integer> stack2=new ArrayDeque<>();
    ListNode res=new ListNode(-1);
    while(l1!=null){
        stack1.push(l1.val);
        l1=l1.next;
    }
    while(l2!=null){
        stack2.push(l2.val);
        l2=l2.next;
    }
    int carry=0;
    while(!stack1.isEmpty() || !stack2.isEmpty() || carry>0){
        int temp=(stack1.isEmpty()?0:stack1.pop())+(stack2.isEmpty()?0:stack2.pop())+carry;
        //头插法
        ListNode next=res.next;
        ListNode newNode=new ListNode(temp%10);
        res.next=newNode;
        newNode.next=next;
        carry=temp/10;
    }
    return res.next;
}

public static ListNode middleNode(ListNode head) {
        if(head==null||head.next==null)return head;
        ListNode fast=head;
        ListNode slow=head;
        // 1 2 3 4 5 6 7
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
}

//递归
public static ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = reverseList(head.next);
    //从后往前
    head.next.next = head;
    head.next = null;
    return newHead;
}

//三指针迭代
public static ListNode reverseList2(ListNode head) {
    if(head==null)return head;
    ListNode pre=head;
    ListNode cur=head.next;
    ListNode temp;
    while(cur!=null){
        temp=cur.next;
        cur.next=pre;
        pre=cur;
        cur=temp;
    }
    head.next=null;
    return pre;
}

public static ListNode reverseBetween(ListNode head, int m, int n) {
    if(m==n) return head;
    //用来遍历
    ListNode pre=head;
    ListNode mid=head.next;
    ListNode rear=null;
    //在遍历的中间连接这个表 时间复杂厚度 O(N)
    //所以需要先保存 m 前的节点用于后面到 n 的时候连接 n 和前面的部分 preM
    //还要保存 m 节点，在后面遍历到 n 的时候将 M 节点和后面的部分连接
    //中间段的前后节点 
    ListNode preM =null;
    ListNode valM=head;
    //ListNode nNext=null;
    int count =1;
    while(count <=n-1){
        //count 的位置实际上是指的 pre 的位置因为只有 pre 是从 head 开始走的
        //尾指针后移
        rear=mid.next;
        if(count==m-1){
            //保存 M 点前面的节点和 M 节点
            preM=pre;
            valM=mid;
            //System.out.println("preM :"+preM.val);
        }
        if(count==n-1){
            //连接 n 后面节点的值
            valM.next=rear;
            //在这里判断下 m 前有没有元素
            if(m==1){
                head=mid;
            } else{
                preM.next=mid;
            }
        }
        if(count >= m && count <=n-1){
            //只有 mid 的位置大于 m 小于等于 n 才会将节点 next 域反转
            mid.next=pre;
        }
        //其他两个指针也向后移动
        pre=mid;
        mid=rear;
        count++;
    }
    return head;
}

func reverseBetween2(head *ListNode, m int, n int) *ListNode {
    dummyNode := &ListNode{
        Val:  -1,
        Next: head,
    }
    mpre := dummyNode //m 节点前的节点
    for i := m; i > 1; i-- {
        mpre = mpre.Next
    }
    pre := mpre
    cur := mpre.Next
    //  2   4
    //1 2 3 4 5
    for i := m; i <= n; i++ {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    mpre.Next.Next = cur //2.next=5
    mpre.Next = pre      //1.next=4
    return dummyNode.Next
}

//头插法
func reverseBetween(head *ListNode, m int, n int) *ListNode {
    dummyNode := &ListNode{
        Val:  -1,
        Next: head,
    }
    mpre := dummyNode //m 节点前的节点
    for i := m; i > 1; i-- {
        mpre = mpre.Next
    }
    cur := mpre.Next
    //1 |2 3 4| 5
    for i := m; i < n; i++ {
        //除非 m=n=len 不然 next 肯定不为空，但是这种情况已经被循环的条件过滤了
        next := cur.Next
        cur.Next = next.Next
        next.Next = mpre.Next
        mpre.Next = next
    }
    return dummyNode.Next
}

Input: 
root = [1, 2, 3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The input and each element of the output are ListNodes, not arrays.
For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null.
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but it's string representation as a ListNode is [].

Input: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

public static ListNode[] splitListToParts(ListNode root, int k) {
    //先要获取下链表的长度
    ListNode temp=root;
    ListNode next=root;
    ListNode [] result=new ListNode[k];
    int count=0;
    while(temp!=null){
        temp=temp.next;
        count++;
    }
    temp=root;
    //任意两部分差距不能大于 1，大的在前，小的在后面
    //其实就是对 count 进行分配
    //注意：有 null 的情况一定是 k>count 直接按 1 切分就完事了
    //k<count 的情况只要在 count/k 的前几个元素上加上 count/k 的余数就行了
    int size=count/k;
    int num=count%k;
    result[0]=root;
    int index=1;
    if(k<=count){
        for (int i=1;temp!=null && index < k;i++){
            next=temp.next;
            if(i<=(size+1)*num && i%(size+1)==0){
                //前几个 res 的分割点
                result[index++]=next;
                //切断
                temp.next=null;
            } else if(i>(size+1)*num && (i-num)%size==0){
                result[index++]=next;
                temp.next=null;
            }
            temp=next;
        }
    } else{
        //剩下的情况就是后面要补 null 的情况
        // 这里两种情况应该是可以合并的，但是 k>count num>0 懒得去抠边界
        for (int i=1;i<k;i++){
            if(temp==null){
                //这个 if 其实没必要
                result[i]=null;
            } else{
                next=temp.next;
                result[i]=next;
                temp.next=null;
                temp=next;
            }
        }
    }
    return result;
}

public ListNode partition(ListNode head, int x) {
    //先在头部加一个 dummy 节点统一操作
    ListNode dummyNode=new ListNode(-1);
    dummyNode.next=head;
    //分割点
    ListNode pre=cutNode=dummyNode;
    ListNode cur=head;
    int cut=0;
    while(cur!=null){
        if(cur.val>=x&&cut==0){
            //只会执行一次在找到第一个 val>=x 的节点的时候---保存分割点
            cutNode=pre;
            cut=1;
        } else if(cur.val<x && cut==1){
            //找到分割点后 遍历到 val<x 的节点的情况---将 cur 连接到 cutNode 的后面 处理好 cur 相邻的两个节点
            //先处理好 cur 相邻的节点
            pre.next=cur.next;
            //连接 cutNode
            cur.next=cutNode.next;
            cutNode.next=cur;
            //cutNode 后移
            cutNode=cur;
        }
        pre=cur;
        cur=cur.next;
    }
    return dummyNode.next
}

public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pA=headA;
    ListNode pB=headB;
    //计算两个链表长度然后计算差距然后向后对齐
    int lenA=0;
    int lenB=0;
    while(pA!=null){
        pA=pA.next;
        lenA++;
    }
    while(pB!=null){
        pB=pB.next;
        lenB++;
    }
    int dis=lenB>lenA?lenB-lenA:lenA-lenB;
    if(lenB>lenA){
        while(dis-->0){
            headB=headB.next;
        }
    } else{
        while(dis-->0){
            headA=headA.next;
        }
    }
    //不相等就一直向后移
    while(headA!=headB){
        //如果有一条为空说明没有交点
        if(headA.next==null){
            return null;
        }
        headA=headA.next;
        headB=headB.next;
    }
    return headA;
}

//方法二 
public static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
    //当一个指针到结尾时转到另一个链表头再向后移动 ，这样做的目的和就是可以直接消除链表之间的长度差，向后对齐，方法还是很巧妙的。
    ListNode pA=headA;
    ListNode pB=headB;
    if(headB==null || headA==null)
                 return null;
    //while(pA!=null && pB!=null ){
    while(pA!=pB){
        //要保证两个==null 的时候都只能执行一次不然如果没有交点就会死循环
        //改变 while 的条件
        //改变 pA，pB 跳转的条件
        //这样就可以保证最后没交点的时候 第二遍循环 pA 和 pB 最后会同时等于 null 会有出口不会死循环
        pA=pA==null?headB:pA.next;
        pB=pB==null?headA:pB.next;
    }
    return pA;
}

public boolean isPalindrome(ListNode head) {
    if(head==null || head.next==null){
        return true;
    }
    // 利用快慢指针找到中点
    ListNode fast = head;
    ListNode slow = head;
    while (fast.next != null) {
        fast = fast.next.next == null ? fast.next : fast.next.next;
        slow = slow.next;
    }
    // 如果是偶数节点，slow 就是偏右的那个 奇数就是正中间的 奇数在正中间不用管
    // fast 是尾节点 1 1 1 1 1 1
    resverList(slow);
    //slow.next==null
    // check
    while (fast != null && head != null) {
        if (fast.val != head.val) {
            return false;
        }
        fast = fast.next;
        head = head.next;
    }
    return true;

}

public static void resverList(ListNode node) {
    ListNode cur = node;
    ListNode pre = null;
    ListNode next = node;
    while (cur != null) {
        next = next.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
}

public  static void deleteNodelow(ListNode node) {
    //思路就是和 node 后面的元素一直交换，就像冒泡排序一样
    ListNode next;
    ListNode temp=new ListNode(0);
    ListNode pre=temp;
    while(node.next!=null){
        next=node.next;
        if(node.next.next==null){
            pre=node;
        }
        //先保存最后一个节点前的节点
        //交换当前节点和后一个节点
        temp.val=node.val;
        node.val=next.val;
        next.val=temp.val;
        node=next;
    }
    pre.next=null;
}

  public  static void deleteNode(ListNode node) {
        node.val=node.next.val;
        node.next=node.next.next;
  }

 public static ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        ListNode dummyHead = new ListNode(0);
        //再头接待你之前加了新的节点
        dummyHead.next = head;
        ListNode pre = dummyHead, cur = head;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
            } else {
                //不是相等的值就向后移动
                pre = cur;
            }
            cur = cur.next;
        }
        return dummyHead.next;
    }

//递归
public static ListNode removeElements2(ListNode head, int val){
    if (head == null)
       return null;
    //将下一个元素放进递归如果是==val 的就会把下一个的下一个元素返回连接到当前元素
    head.next = removeElements2(head.next, val);
    return head.val == val ? head.next : head;
}

public ListNode removeNthFromEnd(ListNode head, int n) {
    if(head==null&&head.next==null) return null;
    //双指针 主要是头和尾的删除需要抠一下边界
    //  -1 | 1 2 3 4 5 6
    ListNode fast=head;
    ListNode dummyNode=new ListNode(-1);
    dummyNode.next=head;
    ListNode slow=dummyNode;
    //加了哑节点，直接先加 1
    int count=1;
    while(fast!=null){
        fast=fast.next;
        slow=count<n?slow:slow.next;
        count++;
        if(fast.next==null){
            //slow 到达需要删除的位置的前一个
            slow.next=slow.next.next;
            return dummyNode.next;
        }
    }
    return dummyNode.next;
}

public  static ListNode deleteDuplicates(ListNode head) {
    if(head==null)return null;
    //首先想到的思路是 3 指针，然后遍历的过程中后面的指针遇到==val 的情况就让后面的指针一直后移走到！=val
    //先添加个哑节点
    ListNode dummyNode=new ListNode(-1);
    dummyNode.next=head;
    ListNode cur=head;
    ListNode next=head.next;
    ListNode pre=dummyNode;
    while(next!=null){
        while(next.val==cur.val){
            next=next.next;
            if(next==null){
                pre.next=null;
                return dummyNode.next;
            }
            if(next.val!=cur.val){
                pre.next=next;
                //cur 跟上
                cur=next;
                break;
            }
        }
        //关键就是 pre 移动这里有坑 不能直接将 pre 移到 cur, 因为会有连续的连续存在
        pre=cur.next!=null&&cur.val==cur.next.val?pre:cur;
        cur=next;
        next=next.next;
    }
    return dummyNode.next;
}

public ListNode deleteDuplicates(ListNode head) {
    if(head==null || head.next==null) return head;
    if(head.val==head.next.val){
        while(head!=null && head.next!=null && head.val==head.next.val){
            head=head.next;
        }
        return deleteDuplicates(head.next); //去重
    }
    head.next=deleteDuplicates(head.next);
    return head;
}

输入：1->1->2
输出：1->2

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

//递归
public ListNode deleteDuplicates(ListNode head) {
    if(head==null || head.next==null) return head;
    ListNode node=deleteDuplicates(head.next);
    if(head.val==node.val) {
        head.next=node.next;
    }
    return head;
}

//迭代
public ListNode deleteDuplicates(ListNode head) {
    ListNode temp = head;
    while (temp != null){
        if (temp.next == null){
            break;
        }
        if (temp.next.val == temp.val){
            temp.next = temp.next.next;
        }else {
            temp = temp.next;
        }

    }
    return head;
}

 输入：[1, 2, 3, 3, 2, 1]
 输出：[1, 2, 3]

 输入：[1, 1, 1, 1, 2]
 输出：[1, 2]

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeDuplicateNodes(head *ListNode) *ListNode {
    var set = make([]bool,20001)
    var dummyNode = &ListNode{Next:head}
    var pre = dummyNode
    for head!=nil{
        if !set[head.Val]{
            set[head.Val]=true
            pre=head
        }else{
            pre.Next=head.Next
        }
        head=head.Next
    }
    return dummyNode.Next
}

public static void reorderList(ListNode head) {
    if(head==null){
        return;
    }
    ListNode right = head;
    ListNode slow = head;
    // 1 1 1 1 1 1 1
    while (right.next != null) {
        right = right.next.next != null ? right.next.next : right.next;
        slow = slow.next;
    }
    // 从 slow 开始翻转
    res(slow);
    //左半部分
    ListNode left = head;
    //下一个节点
    ListNode rnext = right;
    ListNode lnext = left;
    // 1 2 3 4 5 6 7 8 
    // 1 8 2 7 3 6 4 5
    while (right != null && left != null) {
        // 要保存 right 的下一个节点 , left 也需要，不然无法导航到下一个节点
        lnext = lnext.next;
        rnext = rnext.next;
        // 偶数个数节点，如果遍历到 right 链表的最后一个节点
        // 偶数的话 right 链表会短一点 最后连接的时候
        // left: 1->2->3->4->5 right: 8->7->6->5   
        // 像这样会将 5 加到 left 的 4 和 5 之间，但是明显只有一个 5 这样添加就是有问题的
        if(right.next==null){
            //所以这里吧 lnext 赋值为 null, 后面就不会重复连接 5 这个节点
            lnext=null;
        }
        //奇数个数的时候这样连接没问题
        // 1 2 3 4 5 
        // 9 8 7 6 5
        //5.next=5
        left.next = right;
        //如果奇数个数到最后这一步 right 和 left 是同一个节点都为值是 5 的节点
        //所以这里下面的直接覆盖了上面的
        //5.next=null
        right.next = lnext;
        left = lnext;
        right = rnext;
    }
}

//反转
public static void res(ListNode node) {
    ListNode pre = null;
    ListNode cur = node;
    ListNode nex = node;
    while (cur != null) {
        nex = nex.next;
        cur.next = pre;
        pre = cur;
        cur = nex;
    }
}

输入： 1->2->4, 1->3->4
输出： 1->1->2->3->4->4

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode temp=new ListNode(0);
        ListNode res=temp;
        while(l1!=null&&l2!=null){
            if(l2.val<l1.val){
                temp.next=l2;
                l2=l2.next;
                temp=temp.next;
            }else{
                temp.next=l1;
                l1=l1.next;
                temp=temp.next;
            }
        }
        temp.next=l1==null?l2:l1;
        return res.next;
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummyNode=new ListNode(-1);
    mergeTwoLists(l1,l2,dummyNode);
    return dummyNode.next;
}

public void mergeTwoLists(ListNode l1, ListNode l2,ListNode res) {
    if(l1==null){
        res.next=l2;
        return;
    }

    if(l2==null){
        res.next=l1;
        return;
    }

    if(l1.val>l2.val){
        res.next=l2;
        mergeTwoLists(l1,l2.next,res.next);
    }else{
        res.next=l1;
        mergeTwoLists(l1.next,l2,res.next);
    }
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if(l1==null) return l2;
    if(l2==null) return l1;
    ListNode dummyNode=new ListNode(-1);
    if(l1.val<l2.val){
        l1.next=mergeTwoLists(l1.next,l2);
        return l1;
    }else{
        l2.next=mergeTwoLists(l1,l2.next);
        return l2;
    }
}

输入：
[
  1->4->5,
  1->3->4,
  2->6
]
输出：1->1->2->3->4->4->5->6

public ListNode mergeKLists(ListNode[] lists) {
    if(lists.length==0)return null;
    ListNode temp=lists[0];
    for (int i=0;i<lists.length-1;i++){
        temp=merge2List(temp,lists[i+1]);
    }
    return temp;
}

public static ListNode merge2List(ListNode headA,ListNode headB){
    ListNode dummyNode=new ListNode(-1);
    ListNode res=dummyNode;
    ListNode tempA=headA;
    ListNode tempB=headB;
    while(tempB!=null&&tempA!=null){
        if(tempB.val>tempA.val){
            res.next=tempA;
            tempA=tempA.next;
        } else{
            res.next=tempB;
            tempB=tempB.next;
        }
        res=res.next;
    }
    res.next=tempA==null?tempB:tempA;
    return dummyNode.next;
}

public ListNode mergeKLists2(ListNode[] lists) {
    if(lists.length==0)return null;
    return divide(lists,0,lists.length-1);
}

public static ListNode divide(ListNode[] lists,int left,int right){
    if(left>=right)return lists[left];
    int mid=left+((right-left)>>1);
    ListNode l = divide(lists,left,mid);
    ListNode r = divide(lists,mid+1,right);
    return merge2List(l,r);
}

public static ListNode merge2List(ListNode headA,ListNode headB){
    if(headA==null)return headB;
    if(headB==null)return headA;
    ListNode dummyNode=new ListNode(-1);
    ListNode res=dummyNode;
    ListNode tempA=headA;
    ListNode tempB=headB;
    while(tempB!=null&&tempA!=null){
        if(tempB.val>tempA.val){
            res.next=tempA;
            tempA=tempA.next;
        } else{
            res.next=tempB;
            tempB=tempB.next;
        }
        res=res.next;
    }
    res.next=tempA==null?tempB:tempA;
    return dummyNode.next;
}

public ListNode mergeKLists3(ListNode [] lists){
    if (lists.length == 0) {
        return null;
    }
    int k = lists.length;
    while (k > 1) {
        for (int i = 0; i < k / 2; i++) {
            //两两合并将结果保存在前半部分的节点中然后缩小一半的范围
            lists[i] = merge2Lists(lists[i], lists[i + (k + 1) / 2]);
        }
        //缩小一半的范围
        k = (k + 1) / 2;
    }
    return lists[0];
}

//小根堆的方法
public ListNode mergeKLists4(ListNode[] lists) {
    //利用一个按节点值最小次序排列的优先队列，每次取最小的节点加入返回链表中
    if(lists.length < 1) return null;
    Queue<ListNode> pq = new PriorityQueue<>((a, b) -> (a.val - b.val));
    ListNode head = new ListNode(0);
    ListNode cur = head;
    for (ListNode p : lists){
        if(p != null)
        pq.offer(p);
    }
    while(!pq.isEmpty()) {
        cur.next = pq.poll();
        cur = cur.next;
        if(cur.next != null)
        //讲当前节点后一个节点加入队列
        pq.offer(cur.next);
    }
    return head.next;
}

Twitter twitter = new Twitter();

// 用户 1 发送了一条新推文 （用户 id = 1, 推文 id = 5).
twitter.postTweet(1, 5);

// 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。
twitter.getNewsFeed(1);

// 用户 1 关注了用户 2.
twitter.follow(1, 2);

// 用户 2 发送了一个新推文 （推文 id = 6).
twitter.postTweet(2, 6);

// 用户 1 的获取推文应当返回一个列表，其中包含两个推文，id 分别为 -> [6, 5].
// 推文 id6 应当在推文 id5 之前，因为它是在 5 之后发送的。
twitter.getNewsFeed(1);

// 用户 1 取消关注了用户 2.
twitter.unfollow(1, 2);

// 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。
// 因为用户 1 已经不再关注用户 2.
twitter.getNewsFeed(1);

class Twitter {
    //全局时间戳
    private  int timeStamp=0;
    //Tweet 是有序链表，按照时间戳来排序
    private  Map<Integer,Tweet> userTweetMap=new HashMap<>();
    //followMap
    private  Map<Integer,Set<Integer>> userFollowMap=new HashMap<>();;

    public Twitter() {}

    public void postTweet(int userId, int tweetId) {
        Tweet oldHead=userTweetMap.get(userId);
        userTweetMap.compute(userId,(k,v)->new Tweet(tweetId,++timeStamp)).next=oldHead;
    }

    public List<Integer> getNewsFeed(int userId) {
        PriorityQueue<Tweet> pq=new PriorityQueue<>((t1,t2)->t2.time-t1.time);
        List<Integer> feed=new ArrayList<>();
        follow(userId,userId);
        userFollowMap.get(userId).forEach(followerId->Optional.ofNullable(userTweetMap.get(followerId)).ifPresent(tw->pq.offer(tw)));
        int count=0;
        while(!pq.isEmpty() && count<10){
            Tweet tw=pq.poll();
            feed.add(tw.twId);
            if(tw.next!=null){
                pq.offer(tw.next);
            }
            count++;
        }
        return feed;
    }

    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        userFollowMap.computeIfAbsent(followerId,k->new HashSet<>()).add(followeeId);
    }

    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        Optional.ofNullable(userFollowMap.get(followerId)).ifPresent(set->set.remove(followeeId));
    }
}

class Tweet{
    int twId;
    int time;
    Tweet next;
    public Tweet(int twId,int time){
        this.twId=twId;
        this.time=time;
    }
}

/*
        这种解法思路还是比较清晰的
        每次有子链的时候就直接把子链遍历到尾 然后添加到链表中形成新主链 把子链的入口节点 child 指定为 null
        然后主链继续向后遍历所以整个遍历的次数就是整个链表元素的个数 O(M)
*/
public static Node flatten1(Node head) {
    if(head==null || head.next==null&&head.child==null){
        return head;
    }
    Node cur=head;
    Node nNext;
    Node child;
    while(cur!=null){
        if(cur.child!=null){
            //有子链表
            child=cur.child;
            //子链表的表头
            nNext=cur.next;
            //主链的下一节点
            //连接子链表
            cur.next=child;
            //主链的下一节点为子链表头
            child.prev=cur;
            //子链表的前驱节点
            //已经拼接到主链，孩子链置为空 （这步还很关键我开始一直忘设置为 null）
            cur.child=null;
            if(nNext==null){
                //遍历到主链最后一个了
                //所以没有下一个节点，后面的步骤不用继续但是也不能 Break 因为最后一个节点有可能还有子链表
                continue;
            }
            while(child.next!=null){
                //找到新主链的下一节点 （子链的最后一个）
                child=child.next;
            }
            //连接以前的主链
            child.next=nNext;
            nNext.prev=child;
        }
        //主链表向后移动
        cur=cur.next;
    }
    return head;
}

    //标准的 DFS
    public static Node flatten2(Node node) {
       if(node==null){
            return node;
        }
        Node head = node;
        while (head!=null){
            //我感觉这样会快一些
             Node next = head.next;
            if(head.child!=null){
                next = head.next;
                //子链表扁平化 返回头节点
                Node nextLayer = flatten2(head.child);//子链表的头节点
                //连接子链表头和主链
                head.next = nextLayer;
                nextLayer.prev = head;
                //然后子链表置为 null
                head.child = null;
                //遍历到子链表的结尾
                while (nextLayer.next!=null){
                    nextLayer = nextLayer.next;
                }
                //连接子链表的尾部
                nextLayer.next = next;
                if(next!=null){
                    next.prev = nextLayer;
                }
            }
            //这里就直接跳过子链表 之前的是 head=head.next; 但是因为之前的子链表已经加到主链表中所以会浪费一些时间（子链表肯定是已经扁平化的肯定都没有子链表）
            head = next;
        }
        return node;
    }

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

输入： head = [1,2], pos = 0
输出： true
解释： 链表中有一个环，其尾部连接到第一个节点。

输入： head = [1], pos = -1
输出： false
解释： 链表中没有环。

public static Boolean hasCycle(ListNode head) {
    if (head == null || head.next == null)
                  return false;
    //快慢指针 相遇的时候快指针回到头部 step 改为 1 再次相遇的时候就是环的 pos
    //这题只是判断有没有环所以只要相遇就有环
    ListNode slow=head;
    ListNode fast=head.next;
    while(slow!=fast){
        //有环是不会走到尽头的
        if(fast.next==null || fast.next.next==null){
            return false;
        }
        fast=fast.next.next;
        slow=slow.next;
    }
    return true;
}

//UPDATE：2020.9.7 实行重写所有链表题的计划
// A-->B-->C-->D   B 为入环点，D 为相遇点，相遇时 slow = AD, fast = AD+DB+BD
// fast = 2*slow ==> AD = DB + BD ==> AB+BD = DB+BD ==> AB = DB
func detectCycle(head *ListNode) *ListNode {
    var fast, slow = head, head
    for fast!=nil && fast.Next!=nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == nil { //无环
            return nil
        }
        if fast == slow { //有环，next 一定不为 null
            for head!=fast {
                head = head.Next
                fast = fast.Next
            }
            return head
        }
    }
    return nil
}

输入：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