算法--链表

237删除链表中的节点

节点node 无法指向上一个节点, 但是直到当前next 节点, 可以将他的下一个节点值覆盖本身, 并将它的next 指向next.next 节点, 由此删除该节点

    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

206反转链表

解法一, 使用递归

递归过程

    public ListNode reverseList(ListNode head) {
        System.out.println(head.val);
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);  
        head.next.next = head;
        head.next = null;
        return newHead;
    }

解法二, 使用迭代

    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }

141环形链表

    // 利用快慢指针slow, fast, 套圈, 复杂度O(n)
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }