/** 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 示例： 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明： 给定的 n 保证是有效的。 进阶： 你能尝试使用一趟扫描实现吗？ */ public ListNode removeNthFromEnd(ListNode head, int n){ ListNode dummy = new ListNode(0); dummy.next = head; int length = 0; ListNode first = head; while (first != null) { length++; first = first.next; } length -= n; first = dummy; while (length > 0) { length--; first = first.next; } first.next = first.next.next; return dummy.next; }
方法二：一次遍历算法
算法
上述算法可以优化为只使用一次遍历。我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n+1n+1 步，而第二个指针将从列表的开头出发。现在，这两个指针被 nn 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 nn 个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。
public ListNode removeNthFromEnd(ListNode head, int n){ ListNode dummy = new ListNode(0); dummy.next = head; ListNode first = dummy; ListNode second = dummy; // Advances first pointer so that the gap between first and second is n nodes apart for (int i = 1; i <= n + 1; i++) { first = first.next; } // Move first to the end, maintaining the gap while (first != null) { first = first.next; second = second.next; } second.next = second.next.next; return dummy.next; }
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Note that an empty string is also considered valid.
// Hash table that takes care of the mappings. private HashMap<Character, Character> mappings;
// Initialize hash map with mappings. This simply makes the code easier to read. publicSolution(){ this.mappings = new HashMap<Character, Character>(); this.mappings.put(')', '('); this.mappings.put('}', '{'); this.mappings.put(']', '['); }
publicbooleanisValid(String s){
// Initialize a stack to be used in the algorithm. Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) { char c = s.charAt(i);
// If the current character is a closing bracket. if (this.mappings.containsKey(c)) {
// Get the top element of the stack. If the stack is empty, set a dummy value of '#' char topElement = stack.empty() ? '#' : stack.pop();
// If the mapping for this bracket doesn't match the stack's top element, return false. if (topElement != this.mappings.get(c)) { returnfalse; } } else { // If it was an opening bracket, push to the stack. stack.push(c); } }
// If the stack still contains elements, then it is an invalid expression. return stack.isEmpty(); } }
