【每日三题】2021-3-27 LeetCode 19-21

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

思路：快慢指针，两个指针之间相差n + 1个位置。

当快指针到达链表末尾时，慢指针的下一个结点就是要删除的倒数第N个结点。

考虑到删除头结点的情况，引入一个virtual head指针指向整个链表的头部。

当快指针先行过程中遇到末尾，则说明链表长度

代码：

public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null) {
        return head;
    }
    if (head.next == null) {
        return null;
    }
    ListNode virtualHead = new ListNode(-1);
    virtualHead.next = head;
    ListNode ahead = virtualHead, ptr = head;
    for (int i = 0; i < n; i++) {
        if (ptr == null) {
            return head;
        }
        ptr = ptr.next;
    }
    while (ptr != null) {
        ptr = ptr.next;
        ahead = ahead.next;
    }
    if (ahead.val == -1) {
        return head.next;
    }
    ahead.next = ahead.next.next;
    return head;
}

时间复杂度：O(N)

空间复杂度：O(1)

20.有效的括号

思路：使用栈来进行匹配，遇到前括号时就入栈。

遇到后括号时，从栈中d出前一个前括号进行匹配。

代码：

public boolean isValid(String s) {
    if (s.length() % 2 == 1) {
        return false;
    }
    int index = 0;
    Deque<Character> stack = new LinkedList<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) {
                return false;
            }
            char former = stack.pop();
            switch (c) {
                case ')':
                    if (former != '(') {
                        return false;
                    }
                    break;
                case ']':
                    if (former != '[') {
                        return false;
                    }
                    break;
                case '}':
                    if (former != '{') {
                        return false;
                    }
                    break;
                default:
                    return false;
            }
        }
    }
    return stack.isEmpty();
}

时间复杂度：O(N)

空间复杂度：O(N)

21.合并两个有序链表

思路：使用双指针，比较两个链表中当前位置元素的大小。

将较小的一个放入结果链表中，并更新指针。

最后将有剩余的链表整体添加到结果尾部。

代码：

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null) {
        return list2;
    }
    if (list2 == null) {
        return list1;
    }
    ListNode head = new ListNode(-1), ptr = head;
    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            ptr.next = list1;
            ptr = ptr.next;
            list1 = list1.next;
        } else {
            ptr.next = list2;
            ptr = ptr.next;
            list2 = list2.next;
        }
    }
    if (list1 != null) {
        ptr.next = list1;
    }
    if (list2 != null) {
        ptr.next = list2;
    }
    return head.next;
}

时间复杂度：O(m+n)

空间复杂度：O(1)