leetcode刷面试题(面试题02合集)

这一大块都是链表的练习。

面试题 02.01. 移除重复节点

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:

输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
示例2:

输入：[1, 1, 1, 1, 2]
输出：[1, 2]
提示：

链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。
进阶：

如果不得使用临时缓冲区，该怎么解决？

//利用额外空间，hashset保存重复值
public ListNode removeDuplicateNodesOld(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    HashSet<Integer> set = new HashSet<>();
    set.add(head.val);
    ListNode pre = head;
    ListNode node = pre.next;
    while (node != null) {
        if (set.contains(node.val)) {
            node = node.next;
            pre.next = node;
        } else {
            set.add(node.val);
            pre = node;
            node = node.next;
        }
    }
    return head;
}

//不利用额外空间,O(n*n)
public ListNode removeDuplicateNodes(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode fNode = head;
    while (fNode != null) {
        ListNode sNode = fNode.next;
        ListNode pNode = fNode;
        while (sNode != null) {
            if (sNode.val == fNode.val) {
                sNode = sNode.next;
                pNode.next = sNode;
            } else {
                pNode = sNode;
                sNode = sNode.next;
            }
        }
        fNode = fNode.next;
    }
    return head;
}	

面试题 02.02. 返回倒数第 k 个节点
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意：本题相对原题稍作改动

示例：

输入： 1->2->3->4->5 和 k = 2
输出： 4
说明：

给定的 n 保证是有效的。

public int kthToLast(ListNode head, int k) {
    //找到第k+1个节点
    ListNode eNode = head;
    for (int i = 0; i < k; i++) {
        eNode = eNode.next;
    }
    ListNode node = head;
    //让第一个节点和第k个节点一起往后移动
    while (eNode != null) {
        node = node.next;
        eNode = eNode.next;
    }
    return node.val;
}

面试题 02.03. 删除中间节点

实现一种算法，删除单向链表中间的某个节点（除了第一个和最后一个节点，不一定是中间节点），假定你只能访问该节点。

示例：

输入：单向链表a->b->c->d->e->f中的节点c
结果：不返回任何数据，但该链表变为a->b->d->e->f

解答：这道题很有意思的就是，不能找到节点的前一个节点，所以不可能删除本节点，那就删除下一个节点，把本节点的值改成下一个节点，也算是删除本节点了

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

面试题 02.04. 分割链表

编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的 节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之前(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。

示例:

输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8

public ListNode partition(ListNode head, int x) {
    ListNode left = null;
    ListNode leftLast = null;
    ListNode right = null;
    ListNode rightLast = null;
    while (head != null) {
        if (head.val < x) {
            if (left == null) {
                left = new ListNode(head.val);
                leftLast = left;
            } else {
                leftLast.next = new ListNode(head.val);
                leftLast = leftLast.next;
            }
        } else {
            if (right == null) {
                right = new ListNode(head.val);
                rightLast = right;
            } else {
                rightLast.next = new ListNode(head.val);
                rightLast = rightLast.next;
            }
        }
        head = head.next;
    }
    if (left == null) {
        return right;
    } else {
        leftLast.next = right;
        return left;
    }
}

面试题 02.05. 链表求和

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

示例：

输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912

进阶：假设这些数位是正向存放的，请再做一遍。

示例：

输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    int add = (l1.val + l2.val) / 10;
    l1.val = (l1.val + l2.val) % 10;
    ListNode ans = l1;
    while (l1.next != null) {
        l1 = l1.next;
        l2 = l2.next;
        if (l2 == null) {
            if (add == 0) {
                return ans;
            }
            addOne(l1);
            return ans;
        }
        int all = add + l1.val + l2.val;
        l1.val = all % 10;
        add = all / 10;
    }
    if (l2.next != null) {
        l1.next = l2.next;
        if (add != 0) {
            addOne(l1.next);
        }
    } else if (add > 0) {
        l1.next = new ListNode(1);
    }

    return ans;
}

private void addOne(ListNode l1) {
    if (l1.val < 9) {
        l1.val++;
    } else {
        l1.val = 0;
        if (l1.next == null) {
            l1.next = new ListNode(1);
        } else {
            addOne(l1.next);
        }
    }
}

自己试了(假设这些数位是正向存放的)，思想就是，平级才相加，测试了几个用例，都是可以的

public ListNode addTwoNumbersT(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    int deep1 = getDeep(l1);
    int deep2 = getDeep(l2);
    if (deep1 >= deep2) {
        int v = addTwo(l1, l2, deep1, deep2);
        if (v == 0) {
            return l1;
        }
        ListNode node = new ListNode(1);
        node.next = l1;
        return node;
    } else {
        int v = addTwo(l2, l1, deep2, deep1);
        if (v == 0) {
            return l2;
        }
        ListNode node = new ListNode(1);
        node.next = l2;
        return node;
    }

}

private int getDeep(ListNode l1) {
    if (l1 == null) {
        return 0;
    }
    return 1 + getDeep(l1.next);
}

//加操作
private int addTwo(ListNode l1, ListNode l2, int deep1, int deep2) {
    if (l1 == null) {
        return 0;
    }
    if (deep1 == deep2) {
        //平级的话，加上
        int add = addTwo(l1.next, l2.next, deep1 - 1, deep2 - 1);
        int all = add + l1.val + l2.val;
        l1.val = all % 10;
        return all / 10;
    } else {
        //如果不平级，只判断有没有借的
        int add = addTwo(l1.next, l2, deep1 - 1, deep2);
        int all = add + l1.val;
        l1.val = all % 10;
        return all / 10;
    }
}

面试题 02.06. 回文链表

编写一个函数，检查输入的链表是否是回文的。

示例 1：

输入： 1->2
输出： false
示例 2：

输入： 1->2->2->1
输出： true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

答：看了下其他人的算法，都是把后半部的链表进行翻转，好像就我不一样

boolean ans = true;
public boolean isPalindrome(ListNode head) {
    if (head == null) {
        return true;
    }
    ListNode other = head;
    check(other, head);
    return ans;
}

//l2是正向链表随着递归，依次拿到next，在没有pre的情况下，那就倒过来用，每次返回next来给上级用
private ListNode check(ListNode l1, ListNode l2) {
    if (l2.next == null) {
        if (l1.val != l2.val) {
            ans = false;
        }
        return l1.next;
    } else {
        ListNode l = check(l1, l2.next);
        if (l.val != l2.val) {
            ans = false;
        }
        return l.next;
    }

}

面试题 02.07. 链表相交
给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

如果两个链表没有交点，返回 null 。
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

三次递归，符合时间复杂度，只新增deep1和deep2，符合内存要求

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    int deep1 = getDeep(headA);
    int deep2 = getDeep(headB);
    if (deep1 > deep2) {
        for (int i = 0; i < deep1 - deep2; i++) {
            headA = headA.next;
        }
    }
    if (deep2 > deep1) {
        for (int i = 0; i < deep2 - deep1; i++) {
            headB = headB.next;
        }
    }
    return getAns(headA, headB);
}

private ListNode getAns(ListNode headA, ListNode headB) {
    if (headA == null) {
        return null;
    }
    if (headA != headB) {
        return getAns(headA.next, headB.next);
    } else {
        return headA;
    }
}

private int getDeep(ListNode l1) {
    if (l1 == null) {
        return 0;
    }
    return 1 + getDeep(l1.next);
}

面试题 02.08. 环路检测

给定一个有环链表，实现一个算法返回环路的开头节点。
有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。

示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

进阶：
你是否可以不用额外空间解决此题？

这道题我做过，虽然一时忘了怎么做，但是最后还是想起来了。
142. 环形链表 II，这里有图，更容易理解。
我的想法是快慢步，快的一次走两步，慢的走一步，当相交时，慢的走的步数=k环的周长(不一定是1圈)。
如果从交点倒过来走，就能回经过交叉口，就是环的起点，可是不能倒过来走，那就从交点继续前进，另一个从起点前进，两个点总有一天会遇到一起(因为两者差距是k圈长)，而遇到的那一个节点，就是环的起点。

public ListNode detectCycle(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        //快慢步相遇的一天，快的比慢的多走k*圈数,那慢步就走了k*圈数
        if (fast == slow) {
            //分别从起点和交点出发，找到新交点，这个新的交点就是起点(它们都会一起走到原交点，所以肯定相交)
            return getAns(head, fast);
        }
    }
    return null;
}

private ListNode getAns(ListNode headA, ListNode headB) {
    if (headA != headB) {
        return getAns(headA.next, headB.next);
    } else {
        return headA;
    }
}