算法 | 第2章链表相关《程序员面试金典》

作者: 多氯环己烷 | 来源:发表于2021-10-14 14:12 被阅读0次

前言

本系列笔记主要记录笔者刷《程序员面试金典》算法的一些想法与经验总结，按专题分类，主要由两部分构成：经验值点和经典题目。其中重点放在经典题目上；

0. *经验总结

0.1 程序员面试金典 P79

链表的特点：无法在常数时间复杂度内访问链表的特定元素；可以在参数事件复杂度内加入和删除元素；
如果链表被多个对象引用，当链表头结点变了，可能会有一些对象仍然指向原头结点；解决方法：可以用LinkedList封装Node类，该类只包含一个成员变量：头结点；
链表问题可以关注“快慢指针”和递归；

0.2 需要询问面试官的点

是否可以修改原链表；
是否可以开辟额外空间；
时间优先还是空间优先；
在面试中要弄清单向链表和双向链表；

0.3 快慢指针

快慢指针又称双指针，是一个广泛的概念，只要涉及两个指针遍历链表，并且一前一后，都可以称为快慢指针；
快慢指针在不同题目有不同的作用，常见类型有：
- 找到中点：慢指针每走n步时，快指针走2n步，当快指针达到尾部时；
- 找到三分之一点：慢指针走n步，快指针走3n步；
- 找到倒数第x个节点：快指针先走x步后，慢指针从头出发，与快指针速度一样，当快指针达到尾部时，慢指针到倒数第k个节点；【详情见 2. 返回倒数第 k 个节点】
- 测试环形链表：慢指针每走n步时，快指针走2n步，能相遇说明环形；
- 测试链表是否成环并找到第一个成环节点：【详情见 8. 环路检测】
- ……

0.4 递归

实际上所有递归算法都可以转换成迭代法，只是后者可能要复杂得多；
一般来说，递归解法更简洁，但效率低下；

1. 移除重复节点 [easy]

移除重复节点

1.1 考虑点

需要问清楚面试官是否可以开辟额外空间；
需要询问面试官时间优先还是空间优先；

1.2 解法

1.2.1 集合法

public ListNode removeDuplicateNodes(ListNode head) {
    if(head == null || head.next == null){
        return head;
    }
    ListNode cur = head;
    ListNode index = head;
    Set<Integer> set = new HashSet<>();
    set.add(head.val);
    while( cur.next != null){
        cur = cur.next;
        if( !set.contains(cur.val) ){
            index.next = cur;
            index = cur;
            set.add(cur.val);
        } else {
            index.next = null;
        }
    } 
    return head;
}

执行时间：66.09%；内存消耗：51.20%；
也可以用哈希表；
时间复杂度：O(N)，其中 N 是给定链表中节点的数目；
空间复杂度：O(N)。在最坏情况下，给定链表中每个节点都不相同，哈希表中需要存储所有的 N个值；

1.2.2 两循环法

public ListNode removeDuplicateNodes(ListNode head) {
    ListNode ob = head;
    while (ob != null) {
        ListNode oc = ob;
        while (oc.next != null) {
            if (oc.next.val == ob.val) {
                oc.next = oc.next.next;
            } else {
                oc = oc.next;
            }
        }
        ob = ob.next;
    }
    return head;
}

执行时间：93.52%；内存消耗：93.52%；
时间复杂度：O(N²)，其中 N 是给定链表中节点的数目；
空间复杂度：O(1)；

2. 返回倒数第 k 个节点 [easy]

返回倒数第 k 个节点

2.1 考虑点

需要问清楚面试官是否可以开辟额外空间；

2.2 解法

2.2.1 双指针同步运动法（快慢指针）（优）

public int kthToLast(ListNode head, int k) {
    if(head == null || head.next == null){
        return head.val;
    }
    ListNode cur = head;
    ListNode index = head;
    //cur先走k-1个步长
    for(int i = 0; i < k - 1; i++ ){
        cur = cur.next;
    }
    //index上链表，跟cur同步运动，当cur到达链表尾时，cur为倒数第k个
    while(cur.next != null){
        cur = cur.next;
        index = index.next;
    }
    return index.val;
}

执行时间：100.00%；内存消耗：30.78%；
第一个指针先移动k步，然后第二个指针再从头开始，这个时候这两个指针同时移动，当第一个指针到链表的末尾的时候，返回第二个指针即可；

2.2.2 使用栈法

public int kthToLast(ListNode head, int k) {
    Stack<ListNode> stack = new Stack<>();
    //链表节点压栈
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
    //在出栈串成新的链表
    ListNode firstNode = stack.pop();
    while (--k > 0) {
        ListNode temp = stack.pop();
        temp.next = firstNode;
        firstNode = temp;
    }
    return firstNode.val;
}

执行时间：9.00%；内存消耗：58.84%；
把原链表的结点全部压栈，然后再把栈中最上面的k个节点出栈，出栈的结点重新串成一个新的链表即可；

2.2.3 递归

int size;
public int kthToLast(ListNode head, int k) {
    if (head == null){
        return 0;
    }
    int value = kthToLast(head.next, k);
    if (++size == k){
        return head.val;
    }
    return value;
}

执行时间：100.00%；内存消耗：24.44%；
递归访问整个链表，到达尾部时，回传一个设置为0的size计数器，后续调用每次都会将计数器加1，当计数器为k是，即为倒数第k个。value为暂存的结果值；

3. 删除中间节点 [easy]

删除中间节点

3.1 考虑点

题目有点“脑筋急转弯”的意思，注意给出的是当前要删除的节点；
面试官期待的是：当待删除的节点为链表尾节点时的情况：
- 因为不能访问前一个节点，要从其他方面考虑解决方法；
- 可以考虑将该节点标记为假节点，即物理上存在，逻辑上不在；

3.2 解法

3.2.1 复制自己法

public void deleteNode(ListNode node) {
    if(node == null || node.next == null){
        return;
    }
    ListNode nextNode = node.next;
    node.val = nextNode.val;
    node.next = nextNode.next;
}

执行时间：100.00%；内存消耗：72.05%；
如果只能访问当前节点，那么该题的解题思路就是，将自己变成其他节点；
- 举个例子：A->B->C->D；
- 如果要删掉 B 节点，那么只需要将 B 变为 C，再把 B 的指针指向 D，即可完成；

4. 分割链表 [medium]

分割链表

4.1 考虑点

注意题目意思，可以排序，但不一定是排序；
如果本题描述的是数组，对于如何移动元素要谨慎，数组元素的移动通常开销很大。但链表相对比较简单；

4.2 解法

4.2.1 双指针逐个处理法

public ListNode partition(ListNode head, int x) {
    if(head == null || head.next == null ){
        return head;
    }
    //找到比x小的节点，该节点离x节点最近
    ListNode index = head;
    while(index.val < x && index.next != null){
        index = index.next;
    }
    //用2个指针完成移位操作
    //index为首个大于等于x的节点
    //cur为index2的next
    ListNode cur = index.next;
    while(index.next != null){
        if(cur.val >= x){
            //继续
            index = index.next;
            cur = cur.next;
        } else {
            //移位
            index.next = cur.next;
            if( head.val < x){
                cur.next = head.next;
                head.next = cur;
            } else {
                cur.next = head;
                head = cur;
            }
            cur = index.next;
        }
    }
    return head;
}

执行时间：100.00%；内存消耗：64.81%；

4.2.2 排序法

public ListNode partition(ListNode head, int x) {
    return sortList(head, null);
}

private ListNode sortList(ListNode head, ListNode tail) {
    //无法继续拆分的情况
    if (head == null) {
        return null;
    }
    //无法继续拆分的情况
    if (head.next == tail) {
        head.next = null;
        return head;
    }
    //快慢指针找到中间节点
    ListNode slow = head, fast = head;
    while (fast != tail && fast.next != tail) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode mid = slow;
    //左边继续拆分
    ListNode left = sortList(head, mid);
    //右边继续拆分
    ListNode right = sortList(mid, tail);
    //有序链表合并
    return merge(left, right);
}

private ListNode merge(ListNode left, ListNode right) {
    ListNode mergeNode = new ListNode();
    ListNode help = mergeNode;
    //比较两个链表当前的值，值小的链表就把引用赋给mergeNode，并向后移动一位重新赋值给自己，同时help指向值小的那个节点
    while (left != null && right != null) {
        if (left.val < right.val) {
            help.next = left;
            left = left.next;
        } else {
            help.next = right;
            right = right.next;
        }
        help = help.next;
    }
    //最后如果有剩余的节点，就一次性链上去 
    help.next = left == null ? right : left;
    return mergeNode.next;
}

执行时间：100.00%；内存消耗：83.65%；
最无脑的做法是排序，这题不管x给什么，只需要对链表进行一次排序，既能满足题目要求，之前的题目中有练习过插入排序、归并排序，随便哪一种都可以，当然归并的效率更高一点；

4.2.3 头插法

public ListNode partition(ListNode head, int x) {
    ListNode dummy = new ListNode();
    dummy.next = head;
    while (head != null && head.next != null) {
        int nextVal = head.next.val;
        if (nextVal < x) {
            ListNode next = head.next;
            head.next = head.next.next;
            next.next = dummy.next;
            dummy.next = next;
        } else {
            head = head.next;
        }
    }
    return dummy.next;
}

执行时间：100.00%；内存消耗：20.44%；
逐个遍历，遇到小于x值的节点，就插到头部；
PS：Java中HashMap，jdk1.8之前，扩容时链表采用的就是头插法（存在死循环的问题，1.8改了）；

4.2.4 原地删除

public ListNode partition(ListNode head, int x) {
    ListNode dummy = new ListNode();
    dummy.next = head;
    ListNode smallDummy = new ListNode();
    ListNode small = smallDummy;
    //和删除节点的套路一样，先处理头节点满足条件的情况
    while (head != null) {
        if (head.val >= x) {
            break;
        }
        small.next = new ListNode(head.val);
        small = small.next;
        head = head.next;
    }
    //删除
    ListNode cur = head;
    ListNode pre = null;
    while (cur != null) {
        if (cur.val < x) {
            pre.next = cur.next;
            small.next = new ListNode(cur.val);
            small = small.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    small.next = head;
    return smallDummy.next;
}

执行时间：100.00%；内存消耗：56.22%；
按照删除节点的方式，遇到小于x值的节点，就从原链表中删除，并添加到新的链表中，这样一次遍历结束后，只要把新的链表连上原链表即可；

5. 链表求和 [medium]

链表求和

5.1 考虑点

需要考虑链表长度不一导致的空指针异常问题；
进阶的思考：
- 链表长度不一时的对位问题，如（1 -> 2 -> 3 -> 4）和（5 -> 6 -> 7），这里5对2而不是1；
- 上述问题可以遍历链表，用0占位解决；

5.2 解法

5.2.1 反向存放法

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if( l1 == null && l2 == null){
        return null;
    }
    ListNode cur1 = l1;
    ListNode cur2 = l2;
    int cache = 0;
    boolean isFirst = true;
    ListNode head = null;
    ListNode index = null;
    while( cur1 != null || cur2 != null){
        //加法
        int value = 0;
        if( cur1 == null){
            value = cur2.val + cache;
            cur2 = cur2.next;
        } else if ( cur2 == null){
            value = cur1.val + cache;
            cur1 = cur1.next;
        } else {
            value = cur1.val + cur2.val + cache;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        //进位在cache储存
        cache = value / 10;
        //构造新节点，新节点指向新节点
        ListNode node = new ListNode(value%10);
        if(isFirst){
            head = node;
            index = node;
            isFirst = false;
        } else {
            index.next = node;
            index = node;
        }
    }
    //判断cache
    if(cache != 0){
        ListNode node = new ListNode(cache);
        index.next = node;
    }
    return head;
}

执行时间：97.51%；内存消耗：33.72%；
通常做法：逐个遍历，进位，构建新节点；

5.2.2 递归法

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(0);
    helper(head, l1, l2, 0);
    return head.next;
}
private void helper(ListNode result, ListNode l1, ListNode l2, int carry) {
    if (l1 == null && l2 == null && carry == 0){
        return;
    }
    int sum = (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0) + carry;
    result.next = new ListNode(0);
    result.next.val = sum % 10;
    carry = sum / 10;
    helper(result.next, l1 != null ? l1.next : null, l2 != null ? l2.next : null, carry);
}

执行时间：100.00%；内存消耗：26.25%；

6. 回文链表 [easy]

回文链表

6.1 考虑点

对于链表，可以思考的角度有：改变链表方向、拼接、成环等；
需要问清楚面试官是否可以开辟额外空间；
需要问清楚面试官是否可以修改链表；

6.2 解法

6.2.1 改变方向双向遍历法（优）

public boolean isPalindrome(ListNode head) {
    if(head == null){
        return true;
    }
    //统计链表长度
    ListNode cur = head;
    int count = 0;
    while( cur != null ){
        count++;
        cur = cur.next;
    }
    if( count < 2){
        return true;
    }
    //改变前 count/2-1 个节点指向，分奇偶讨论
    ListNode right = head;
        //定位right指针
    if( count % 2 == 1 ){
        //奇数情况
        for( int i = 0; i < count/2+1; i++){
            right = right.next;
        }
    } else {
        //偶数情况
        for( int i = 0; i < count/2; i++){
            right = right.next;
        }
    }
    //改变前count/2-1个节点方向
    ListNode left = head;
    cur = head.next;
    ListNode mid = cur.next;
    //判断对只有2~3个节点单独判断
    if(count < 4){
        return left.val == right.val;
    }
    for( int i = 0; i < count/2-1; i++){
        cur.next = left;
        left = cur;
        cur = mid;
        mid = mid.next;
    }
    //遍历比较left和right
    while(right != null){
        if(left.val != right.val){
            return false;
        }
        right = right.next;
        left = left.next;
    }
    return true;
}

执行时间：96.85%；内存消耗：80.19%；
不使用额外空间；
需要注意，是否可以改变原链表；

6.2.2 将值复制到数组中后用双指针法

public boolean isPalindrome(ListNode head) {
    List<Integer> vals = new ArrayList<Integer>();
    // 将链表的值复制到数组中
    ListNode currentNode = head;
    while (currentNode != null) {
        vals.add(currentNode.val);
        currentNode = currentNode.next;
    }
    // 使用双指针判断是否回文
    int front = 0;
    int back = vals.size() - 1;
    while (front < back) {
        if (!vals.get(front).equals(vals.get(back))) {
            return false;
        }
        front++;
        back--;
    }
    return true;
}

执行时间：32.69%；内存消耗：24.77%；
时间复杂度：O(n)，其中 n 指的是链表的元素个数；
- 第一步：遍历链表并将值复制到数组中，O(n)。
- 第二步：双指针判断是否为回文，执行了 O(n/2) 次的判断，即 O(n)。
- 总的时间复杂度：O(2n) = O(n)。
空间复杂度：O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值；
需要开辟额外空间；

6.2.3 递归

private ListNode frontPointer;
private boolean recursivelyCheck(ListNode currentNode) {
    if (currentNode != null) {
        if (!recursivelyCheck(currentNode.next)) {
            return false;
        }
        if (currentNode.val != frontPointer.val) {
            return false;
        }
        frontPointer = frontPointer.next;
    }
    return true;
}
public boolean isPalindrome(ListNode head) {
    frontPointer = head;
    return recursivelyCheck(head);
}

执行时间：56.10%；内存消耗：5.05%；
时间复杂度：O(n)，其中 n 指的是链表的大小；
空间复杂度：O(n)，其中 n 指的是链表的大小。这种方法不仅使用了 O(n)的空间，且比第一种方法更差，因为在许多语言中，堆栈帧的开销很大（如 Python），并且最大的运行时堆栈深度为 1000（可以增加，但是有可能导致底层解释程序内存出错）。为每个节点创建堆栈帧极大的限制了算法能够处理的最大链表大小；

7. 链表相交 [easy]

链表相交

7.1 考虑点

这里不能使用链表反转，题目要求不能破坏原有结构；
对于两条长度不同的链表而言，可以先遍历求出各自的长度再做计算，也可以使用；两个指针走完两条链表，最后必然能重合，因为指针的速度（步长）的一样的；
需要问清楚面试官是否可以开辟额外空间；

7.2 解法

7.2.1 长度对齐双指针法

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if( headA == null || headB == null ){
        return null;
    }
    ListNode cur = headA;
    int countA = 0;
    while( cur != null ){
        countA++;
        cur = cur.next;
    }
    cur = headB;
    int countB = 0;
    while( cur != null){
        countB++;
        cur = cur.next;
    }
    //保证headA长于headB
    if( countA < countB){
        return getIntersectionNode(headB,headA);
    }
    ListNode curA = headA;
    ListNode curB = headB;
    for( int i = 0; i < countA-countB; i++){
        curA = curA.next;
    }
    while( curA != null ){
        if( curA.equals(curB) ){
            return curA;
        }
        curA = curA.next;
        curB = curB.next;
    }
    return null;
}

执行时间：100.00%；内存消耗：57.18%；
时间复杂度：O(A+B)，A和B是两个链表的长度；
空间复杂度：O(1)；

7.2.2 双指针（优）

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
     ListNode h1 = headA;
     ListNode h2 = headB;
     while(h1 != h2){
         h1 = (h1 == null ? headB : h1.next); 
         h2 = (h2 == null ? headA : h2.next); 
     }
     return h1;
}

执行时间：100.00%；内存消耗：57.18%；
对于h1来说，走到末尾（或相交点）时，走了两段链表（两段链表不同部分）的路径；
对于h2来说，走到末尾（或相交点）时，走了两段链表（两段链表不同部分）的路径；
h1和h2走过的路径相同，因此第二轮就能匹配到；

8. 环路检测 [medium]

环路检测

8.1 考虑点

处理环形链表可以试试快慢指针；

8.2 解法

8.2.1 快慢指针法（优）

public ListNode detectCycle(ListNode head) {
    if( head == null ){
        return null;
    }
    if(head.next == null){
        return null;
    }
    if(head.next.next == null){
        return null;
    }
    //使用快慢指针找到有count个环成圈;
    ListNode fast = head.next.next;
    ListNode slow = head.next;
    int count = 1; //count变量不是必要的
    while( fast != slow ){
        if(fast == null || slow == null){
            return null;
        }
        slow = slow.next;
        if(fast.next != null){
            fast = fast.next.next;
        } else {
            return null;
        }
        count++;
    }
    // cur 和 slow 一起走，走n步到环路开头节点
    ListNode cur = head;
    while( cur != slow ){
        cur = cur.next;
        slow = slow.next;
    }
    return cur;
}

执行时间：100.00%；内存消耗：53.71%；
时间复杂度：O(n)，n为不成环的节点和成环节点的较大值；
空间复杂度：O(1)，不开辟额外空间，算法中的count不是必要的；
算法解释：算法主要分为两个部分，如下：
- 使用快慢指针找到有count个环成圈：走x步到达下标为x的节点。可以通过快慢指针获得count（或count的质因数）个节点成圈，同时慢指针走了count步（此时快慢指针所指节点下标为count）。假设环路开头节点的下标为 n（n<=count），从链表头走要走n步到环路开头节点；
- 走n步到环路开头节点：从链表头到快慢指针处走count步，从链表头到环路开头节点要n步。如果要从环路开头节点走到快慢指针处要走count-n步；如果要从环路开头节点再一次回到开头节点必须走完一个圈（或n圈），即走count步。那么从快慢指针处走到开头节点至少就要count-(count-n)=n步，而我们从链表头走到环路开头节点也是要走n步；

8.2.2 哈希表

public ListNode detectCycle(ListNode head) {
    ListNode pos = head;
    Set<ListNode> visited = new HashSet<ListNode>();
    while (pos != null) {
        if (visited.contains(pos)) {
            return pos;
        } else {
            visited.add(pos);
        }
        pos = pos.next;
    }
    return null;
}

执行时间：30.58%；内存消耗：24.80%；
时间复杂度：O(N)，其中 N 为链表中节点的数目。我们恰好需要访问链表中的每一个节点；
空间复杂度：O(N)，其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中；

最后

$\color{blue}{\rm\small{新人制作，如有错误，欢迎指出，感激不尽！}}$

$\color{blue}{\rm\small{欢迎关注我，并与我交流！}}$

$\color{blue}{\rm\small{如需转载，请标注出处！}}$

算法 | 第2章 链表相关《程序员面试金典》

前言