19 Remove Nth Node From End of List
概述
Remove Nth Node From End of List 即删除单向链表中从链表尾部开始的第N个节点。
分析
单向链表只能通过逐步前进才能到达指定节点，是无法在 O(1) 的时间复杂度下拿到链表的长度的，可以考虑通过一次遍历将链表明确节点节点位置与值的对应关系，之后通过链表的节点操作完成删除节点的效果。
节点位置与值的关系可以通过Hash进行存储，由于链表长度不定，预先留出数组空间的方式个人认为并不是好的选择。
解法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
public class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { HashMap<Integer, ListNode> idxListMap = new HashMap<Integer, ListNode>(); ListNode it = head; int i = 1; for(; it != null; it = it.next, ++i) { idxListMap.put(i, it); } if (idxListMap.size() == 1) { return null; } if (n == 1) { idxListMap.get(idxListMap.size() - 1).next = null; return head; } if (n == idxListMap.size()) { head = head.next; return head; } if (idxListMap.containsKey(idxListMap.size() - n) && idxListMap.containsKey(idxListMap.size() - n + 2)) { idxListMap.get(idxListMap.size() - n).next = idxListMap.get(idxListMap.size() - n + 2); } return head; } } |
20 Valid Parentheses
概述
Valid Parentheses 即判断括号是否匹配。
分析
括号需要一一对应，即一个左括号，需要对应一个右括号，简单来说，在字符串遍历过程中，右括号出现之后，需要判断上一个括号是不是一个左括号，如果是一个左括号，那么说明这个括号完成了匹配。否则，说明没有完成匹配。
从数据结构上来说，栈是一个非常适合的数据结构，左括号直接入栈，出现右括号则比较栈顶元素，如果相同，则出栈，继续比较，否则则说明不匹配。完成比较之后，如果栈已空，则说明括号完成了完全的匹配。
但是，使用字符串操作其实也能做到这一效果，完全不需要使用 Java 内置的栈。即栈顶元素可以看成是字符串的最后一个元素，出栈则是删除最后一个字符串。
解法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
public class Solution { public boolean isValid(String s) { String p = ""; for (int i = 0; i < s.length(); ++i) { String c = s.substring(i, i + 1); if ("([{".contains(c)) { p = p + c; continue; } if (")]}".contains(c)) { if (p.length() == 0) { return false; } String topOfStack = p.substring(p.length() - 1, p.length()); if (c.equals(")") && !topOfStack.equals("(")) { return false; } if (c.equals("]") && !topOfStack.equals("[")) { return false; } if (c.equals("}") && !topOfStack.equals("{")) { return false; } p = p.substring(0, p.length() - 1); } } return p.length() == 0; } } |
21 Merge Two Sorted Lists
概述
Merge Two Sorted Lists 即单向链表归并。
分析
归并已排序链表，首先需要判断两个链表是否已经到达链表终点，达到链表终点之后只需要处理另一个没有到达终点的链表。
在两个链表没有到达终点时，比较二者的首节点的值，在升序的情况下，较小的值添加到结果链表中，较小值所在的链表向前前进一个节点，之后周而复始的比较。
解法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null && l2 == null) { return null; } ListNode head = new ListNode(Integer.MIN_VALUE); ListNode it = head; while (l1 != null || l2 != null) { int val = 0; if (l1 == null) { val = l2.val; l2 = l2.next; } else if (l2 == null) { val = l1.val; l1 = l1.next; } else if (l1.val < l2.val) { val = l1.val; l1 = l1.next; } else { val = l2.val; l2 = l2.next; } if (it.val == Integer.MIN_VALUE) { it.val = val; continue; } it.next = new ListNode(val); it = it.next; } return head; } } |