维护不易，还请点赞支持，微信搜索bigsai 回复进群一起打卡。
19删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
分析：
可以扫描两次，第一次获取总长度，知道倒数第N是正数第几个，第二次扫描真正的找到节点删除。
如何扫描一次呢？
可以使用数组(集合)，将所有节点地址存入ArrayList中，根据n找到正数的编号，直接编号前一个next指向编号后一个节点，最终返回头即可，当然要考虑特殊情况比如删除头之类。实现代码：
public ListNode removeNthFromEnd2(ListNode head, int n) { List<ListNode>list=new ArrayList<ListNode>(); ListNode team=head; while (team!=null) { list.add(team); team=team.next; } list.add(null); if(list.size()==n) return head.next; if(list.size()<1)return null; int index=list.size()-1-n; list.get(index-1).next=list.get(index+1); return head; }
还可以怎么考虑？
用两个指针，一个先走N步，然后两个同时向下寻找。一直到右侧的到最尽头即可找到待删除节点。
这样删除并不方便，在具体操作上，要找到待删除的前一个节点，用这个节点删除他的后面节点。而如果待删除的是头节点可能还需要特殊讨论，为了避免这种情况，我们可以使用一个头节点放在最前侧，这样就可以把链表中每一个节点都当作普通节点来处理。
具体代码为：
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode value=new ListNode(0); value.next=head; head=value; ListNode team=value; for(int i=0;i<n;i++) { team=team.next; } while (team.next!=null) { team=team.next; head=head.next; } if(head.next!=null) head.next=head.next.next; return value.next; }
20 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入:
"()"输出: true
示例 2:
输入:
"()[]{}"输出: true
示例 3:
输入:
"(]"输出: false
示例 4:
输入:
"([)]"输出: false
示例 5:
输入:
"{[]}"输出: true
分析：
括号类的问题是经典栈类问题，肯定要想到用栈处理。判断一个字符串满不满足一个有效的字符串，就要看它是不是都能组成对。
- 从单个对来说，
((,))都是不满足的，只有()才可满足，即一左一右。 - 从多个对来说
{[(字符串还可接受任意无限(，[,{的括号。但是只能接收)的向左的括号。
从上面可以看作一种相消除的思想。例如(({[()()]}))字符串遍历时候可以这样处理：
(({[(下一个)消掉成(({[(({[(下一个)消掉成(({[(({[下一个]消掉成(({(({下一个}消掉成((((下一个)消掉成((下一个)消掉成`` 这样就满足题意
所以这个过程利用栈判断当前是加入栈还是消除顶部，到最后如果栈为空说明满足，否则不满足，当然具体括号要对应，具体实现代码为：
public boolean isValid(String s) { Stack<Character>stack=new Stack<Character>(); for(int i=0;i<s.length();i++) { char te=s.charAt(i); if(te==']') { if(!stack.isEmpty()&&stack.pop()=='[') continue; else { return false; } } else if(te=='}') { if(!stack.isEmpty()&&stack.pop()=='{') continue; else { return false; } } else if(te==')') { if(!stack.isEmpty()&&stack.pop()=='(') continue; else { return false; } } else stack.push(te); } return stack.isEmpty(); }
用自带的栈并不是很快，所以我们使用数组模拟栈的实现，这样速度就快了一点：
public boolean isValid(String s) { char a[]=new char[s.length()]; int index=-1; for(int i=0;i<s.length();i++) { char te=s.charAt(i); if(te==']') { if(index>=0&&a[index]=='[') index--; else { return false; } } else if(te=='}') { if(index>=0&&a[index]=='{') index--; else { return false; } } else if(te==')') { if(index>=0&&a[index]=='(') index--; else { return false; } } else a[++index]=te; } return index==-1; }
结语
原创不易，bigsai请你帮两件事帮忙一下:
- star支持一下， 您的肯定是我在平台创作的源源动力。
- 微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。
记得关注、咱们下次再见！
