Letcode刷题记录

452. 用最少数量的箭引爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。
示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。
示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:

• 在x = 2处发射箭，击破气球[1,2]和[2,3]。
• 在x = 4处射出箭，击破气球[3,4]和[4,5]。

提示:

1 <= points.length <= 105
points[i].length == 2
-231 <= xstart < xend <= 231 - 1

解题思路：

1. 初步看是找交集，所以要排序
2. 最大需要射箭 为数组长度次
3. 只要有一个交集就 –， 三个交集就相当于-了两次
4. 注意比较的时候有个坑， 不能用a[0]-b[0] 因为Integer回越界， 而要用a[0]>b[0]?1:-1

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points,(a,b)->{
            return a[0] > b[0]?1:-1;
        });
        int left = points[0][0];
        int right = points[0][1];
        int count = points.length;
        for(int i=1;i<points.length;i++){
            //不相交，一定在左边
            if(right < points[i][0]){
                left = points[i][0];
                right = points[i][1];
                continue;
            }

            //相交，则需要合并成交集，且计数器-1
            left = left < points[i][0] ? points[i][0]:left;
            right = right < points[i][1] ? right:points[i][1];
            count--;
        }
        return count;
    }
}

20. 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([])”

输出：true

提示：

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

思路：

1. 用栈来探入弹出
2. 用字典来记录枚举

class Solution {
    public boolean isValid(String s) {
        char[] sc = s.toCharArray();
        Deque<Character> stack = new LinkedList<>();
        Map<Character,Character> dic = new HashMap<>();
        dic.put('(',')');
        dic.put('[',']');
        dic.put('{','}');
        for(int i=0;i<sc.length;i++){
            Character ano = dic.get(sc[i]);
            if(ano != null){
                stack.push(ano);
            }else{
                if(stack.isEmpty()) return false;
                if(stack.pop() != sc[i]){
                    return false;
                }
            }
        }
        if(stack.isEmpty()){
            return true;
        }
        return false;
    }
}

71. 简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/‘ 开头），请你将其转化为 更加简洁的规范路径。

在 Unix 风格的文件系统中规则如下：

一个点 ‘.’ 表示当前目录本身。
此外，两个点 ‘..’ 表示将目录切换到上一级（指向父目录）。
任意多个连续的斜杠（即，’//‘ 或 ‘///‘）都被视为单个斜杠 ‘/‘。
任何其他格式的点（例如，’…’ 或 ‘….’）均被视为有效的文件/目录名称。
返回的 简化路径 必须遵循下述格式：

始终以斜杠 ‘/‘ 开头。
两个目录名之间必须只有一个斜杠 ‘/‘ 。
最后一个目录名（如果存在）不能 以 ‘/‘ 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘..’）。
返回简化后得到的 规范路径 。

示例 1：

输入：path = “/home/“

输出：”/home”

解释：

应删除尾随斜杠。

示例 2：

输入：path = “/home//foo/“

输出：”/home/foo”

解释：

多个连续的斜杠被单个斜杠替换。

示例 3：

输入：path = “/home/user/Documents/../Pictures”

输出：”/home/user/Pictures”

解释：

两个点 “..” 表示上一级目录（父目录）。

示例 4：

输入：path = “/../“

输出：”/“

解释：

不可能从根目录上升一级目录。

示例 5：

输入：path = “/…/a/../b/c/../d/./“

输出：”/…/b/d”

解释：

“…” 在这个问题中是一个合法的目录名。

思路：

1. 用栈 从左到右 push，要注意空和.， 然后pop控制..

   class Solution{
       public String simplifyPath(String path) {
           String[] pathArray = path.split("/");
           Deque<String> stack = new LinkedList();
           for(int i=0;i<pathArray.length;i++){
               if("".equals(pathArray[i]) || ".".equals(pathArray[i])) continue;
               stack.push(pathArray[i]);
           }
           Deque<String> anotherStack = new LinkedList();
           int cnt = 0;
           while(!stack.isEmpty()){
               String tmp = stack.pop();
               if(tmp.equals("..")){
                   cnt++;
                   continue;
               }
               if(cnt >0){
                   cnt--;
                   continue;
               }
               anotherStack.push(tmp);
           }
           StringBuilder sb = new StringBuilder();
           if(anotherStack.size() == 0) sb.append("/");
           while(!anotherStack.isEmpty()){
               String p = anotherStack.pop();
               if(".".equals(p)) continue;
               sb.append("/");
               sb.append(p);
           }
           return sb.toString();
       }
   }

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.getMin(); –> 返回 -2.

提示：

-231 <= val <= 231 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次

思路：

1. 利用两个Stack数据结构，一个放原值，一个放当前最小值。 peek方法不弹出，看一下，

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack();
        minStack = new Stack();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.isEmpty()){
            minStack.push(val);
            return;
        }

        int former = minStack.peek();
        minStack.push(former < val? former:val);
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

150. 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 ‘+’、’-‘、’*’ 和 ‘/‘ 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = [“2”,”1”,”+”,”3”,”*”]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：

输入：tokens = [“4”,”13”,”5”,”/“,”+”]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：

输入：tokens = [“10”,”6”,”9”,”3”,”+”,”-11”,”“,”/“,”“,”17”,”+”,”5”,”+”]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

1 <= tokens.length <= 104
tokens[i] 是一个算符（”+”、”-“、”*” 或 “/“），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

思路：
利用栈的入和出

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<String> stack = new LinkedList();
        for(int i=0;i<tokens.length;i++){
            if("+".equals(tokens[i]) || "-".equals(tokens[i]) || "*".equals(tokens[i]) || "/".equals(tokens[i])){
                int b = Integer.parseInt(stack.pop());
                int a= Integer.parseInt(stack.pop());
                switch(tokens[i]){
                    case "+": {
                        stack.push(a+b+"");break;
                    }
                    case "-": {
                        stack.push(a-b+"");break;
                    }
                    case "*": {
                        stack.push(a*b+"");break;
                    }
                    case "/": {
                        stack.push(a/b+"");break;
                    }
                }
                continue;
            }
            stack.push(tokens[i]);
        }
        return Integer.parseInt(stack.pop());
    }
}

141. 环形链表

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

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

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

示例 1：

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

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

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

思路：

1. 经典的快慢指针法

   /**
    * Definition for singly-linked list.
    * class ListNode {
    *     int val;
    *     ListNode next;
    *     ListNode(int x) {
    *         val = x;
    *         next = null;
    *     }
    * }
    */
   public class Solution {
       public boolean hasCycle(ListNode head) {
           if(head == null || head.next == null) return false;
           ListNode fast = head.next.next;
           while(true){
               if(head == null || fast == null || fast.next == null) return false;
               if(head == fast){
                   return true;
               }
               fast = fast.next.next;
               head = head.next;
           }
       }
   }

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

思路：
链表后移，累进位

/**
 * 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 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode rst = new ListNode();
        ListNode cur = rst;
        int add = 0;
        while(true){
            cur.next = new ListNode((add + l1.val +l2.val)%10);
            cur = cur.next;
            add = (add + l1.val +l2.val)/10;
            if(l1.next == null && l2.next ==null && add ==0) break;
            l1 = l1.next == null?new ListNode(0):l1.next;
            l2 = l2.next == null?new ListNode(0):l2.next;
        }
        return rst.next;
    }
}

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

思路：

1. 交替比较

   /**
    * 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 {
       public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
           ListNode data = new ListNode(1);
           ListNode cur = data;
           while(true){
               if(list1 == null) list1 = new ListNode(Integer.MAX_VALUE);
               if(list2 == null) list2 = new ListNode(Integer.MAX_VALUE);
               if(list1.val == Integer.MAX_VALUE && list2.val == Integer.MAX_VALUE) break;
   
               if(list1.val < list2.val){
                   cur.next = list1;
                   list1 = list1.next;
                   cur = cur.next;
                   continue;
               }else{
                   cur.next = list2;
                   list2 = list2.next;
                   cur = cur.next;
                   continue;
               }
           }
           cur.next=null;
           return data.next;
       }
   }

138. 随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random –> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random –> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。

思路：
利用HashMap key存放对象指针的特性，利用对象初始化产生指针， 赋值阶段使用指针的两阶段特性。
学习 spring 循环依赖办法，先初始化对象，再赋值对象的两阶段办法。

/*
// 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 {
    public Node copyRandomList(Node head) {
        Map<Node,Node> dic = new HashMap();   // key 旧的  val 新的
        Node cur = head;
        while(cur != null){
            dic.put(cur,new Node(0));
            cur = cur.next;
        }
        cur = head;
        Node rst = new Node(1);
        Node rstCur = rst;
        while(cur != null){
            Node n = dic.get(cur);
            n.val = cur.val;
            n.next = cur.next == null? null:dic.get(cur.next);
            n.random = cur.random == null? null:dic.get(cur.random);
            cur = cur.next;
            rstCur.next = n;
            rstCur = rstCur.next;
        }
        return rst.next;
    }
}

LCR 024. 反转链表

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：

输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]

/**
 * 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 {
    public ListNode reverseList(ListNode head) {
        ListNode left = null;
        ListNode right = head;
        while(right != null){
            ListNode tmp = right.next;
            right.next = left;
            left = right;
            right = tmp;
        }
        return left;
    }
}

92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

思路和易错点：

1. 顺序读取链表，找到反转起始位，反转，重新拼接
2. 反转过程回损坏原链表，要注意
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 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left == right) return head;
        //截取区间链表，并反转，拼接回原链表
        ListNode cur = head;
        int count=1;
        ListNode rev = new ListNode();
        ListNode revCur = rev;
        ListNode rst = new ListNode();
        ListNode rstCur = rst;
        while(cur != null){
            if(count < left){
                rstCur.next = cur;
                rstCur = rstCur.next;
                cur = cur.next;
                count++;
            }else if (count >= left && count <= right){
                revCur.next = cur;
                revCur = revCur.next;
                cur = cur.next;
                count++;
                if(cur == null){
                    revCur.next = null;
                    rev = rever(rev.next);
                    rstCur.next = rev;
                    rstCur = getTail(rstCur);
                    rstCur.next = cur;
                    rstCur = rstCur.next;
                }
            }else if( count == right+1){
                revCur.next = null;
                rev = rever(rev.next);
                rstCur.next = rev;
                rstCur = getTail(rstCur);
                rstCur.next = cur;
                rstCur = rstCur.next;
                cur = cur.next;
                count++;
            }else{
                rstCur.next = cur;
                rstCur = rstCur.next;
                cur = cur.next;
                count++;
            }
        }
        return rst.next;

   }

    public ListNode getTail(ListNode head){
        ListNode rst = new ListNode();
        ListNode cur = head;
        if(cur == null) return cur;
        while(cur.next != null){
            cur = cur.next;
        }
        return cur;
    }

   public ListNode rever(ListNode li){
    ListNode left = null;
    ListNode right = li;
        while(right !=null){
            ListNode tmp = right.next ;
            right.next = left;
            left = right;
            right = tmp;
        }
    return left;
   }
}

19. 删除链表的倒数第 N 个结点

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

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：

输入：head = [1], n = 1
输出：[]
示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

/**
 * 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 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int count = 0;
        ListNode cur = head;
        while(cur != null){
            count++;
            cur= cur.next;
        }
        int former = count - n;
        cur = head;
        count = 0;
        if(former == 0) return head.next;
        while(cur != null){
            count++;
            if(count == former){
                cur.next = cur.next.next;
                break;
            }
            cur = cur.next;
        }
        return head;
    }
}

进阶：你能尝试使用一趟扫描实现吗？
用栈？

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

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：

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

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列

思路：
从头到尾遍历，断开重复的，重新连接即可
注意，之后要把新链表的next 设置位null

/**
 * 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 {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        ListNode rst = new ListNode();
        ListNode rstCur = rst;
        while(cur != null){
            if(cur.next == null){
                rstCur.next = cur;
                rstCur = rstCur.next;
                cur = cur.next;
                continue;
            }
            if(cur.val == cur.next.val){
                ListNode innerCur = cur;
                int v = cur.val;
                while(innerCur != null && innerCur.val == v){
                    innerCur = innerCur.next;
                }
                cur.next = innerCur;
            }else{
                rstCur.next = cur;
                rstCur =rstCur.next;
            }
            cur = cur.next;
        }
        rstCur.next = null;
        return rst.next;
    }
}