链表

链表

反转链表

头条:迭代递归都要写出来。

迭代版本:

public ListNode reverseList(ListNode head) {
    ListNode newHead = new ListNode();

    while (head != null) {
        // 5 -> 4 -> 3
        //
        ListNode tmp = head.next;
        head.next = newHead.next;
        newHead.next = head;
        head = tmp;
    }

    return newHead.next;
}

递归版本。

将链表想象为:head -> 其余部分,那么翻转 其余部分 如何翻转:p = reverseList(head.next)其余部分next 的节点需要指向 headheadnext 节点需要置为 null,以确保 head 变成了末尾节点。最后返回 p 节点。

  • 在写的时候,有一次写成了 p.next = head,这里是不正确的。head.next.next = head; head.next = null 这是真正干活的部分,是真正决策对于两个节点如何翻转的过程部分,其不属于递归。
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

反转链表Ⅱ

美团面试题。

这道题,这篇文章的思路非常简洁易懂,其核心就是采用头插法,可以间接达到反转的效果。下面算法是看过他的思路之后,自己写出来的。

需要注意的地方,看下图 removednext 节点应该调整为 p,即写作 removed.next = p

[pre] -> [p] -> [p.next] -> [p.next.next]
                   ^
                   |
                 removed

第一次调整这样还可以,没有问题,但是第二次调整的时候,当前指针就变为了。这个时候一下就可以看出来 removed.next 就不能指向 p 了,而应该指向的永远都是 pre.nextpre 指针是不变的。

[pre] -> [p.next] -> [p] -> [p.next.next]
                                ^
                                |
                             removed
public ListNode reverseBetween(ListNode head, int left, int right) {
    if (left == right || head == null || head.next == null) {
        return head;
    }

    // [] -> [x] -> [y] -> [z]
    ListNode DUMMY = new ListNode();
    DUMMY.next = head;

    ListNode pre = null;
    ListNode p = DUMMY;
    for (int i = 0; i < left; i++) {
        pre = p;
        p = p.next;
    }

    for (int i = 0; i < right - left; i++) {
        // [pre] -> [p] -> [p.next] -> [p.next.next]
        ListNode removed = p.next;
        ListNode removedNext = removed.next;

        // [pre] -> [p] <-> [p.next]  [p.next.next]
        // 不能这样 removed.next = p;
        removed.next = pre.next;
        //   |--------------|
        //   |              v
        // [pre]  [p] <-> [p.next]  [p.next.next]
        pre.next = removed;
        //   |--------------|
        //   |              v
        // [pre]  [p] <- [p.next]  [p.next.next]
        //         |                     ^
        //         |_____________________|
        p.next = removedNext;
    }

    return DUMMY.next;
}

LRU

  • 底层数据结构是 Mapkey 就是用户传入的 key,而 value 则是通过 ListNode 来封装起来。当前所有的 <key, value> 对通过双向链表来串起来,head 节点是最近一次刚刚访问过的,而 tail 是很长时间都没有访问过的。
[key1, value1]
[key2, value2]
...
[keyn, valuen]

[key1, value1] <--> [key2, value2] <--> ... [keyn, valuen]

所有的操作基本上核心的就是调整键值对在双向链表上的顺序。

  • 第一次 put 的时候,insertAtHead
  • 第二次 put 的时候,即 updateValue 的时候,moveToHead 做的操作,首先 removeNode,然后重新 insertAtHead
  • 为了保证 remove 的复杂度是 O(1),我们需要将 ListNode 实现为双向链表
  • get 的时候,moveToHead

通过借助 DUMMY_HEADDUMMY_TAIL,我们能够减轻处理特殊 case 编码的复杂度。

class LRUCache {
    
    private Map<Integer, ListNode> cache = new HashMap();

    // 先实现一个 remove() 复杂度是 O(1) 的双向链表
    // head 是 rencently 的,tail 是即将淘汰的
    
    ListNode DUMMY_HEAD = new ListNode(-1, -1);
    ListNode DUMMY_TAIL = new ListNode(-1, -1);
    
    {
        DUMMY_HEAD.next = DUMMY_TAIL;
        DUMMY_TAIL.prev = DUMMY_HEAD;
    }
    
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        ListNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        ListNode node = cache.get(key);
        
        if (node == null) {
            if (cache.size() == capacity) {
                ListNode tailNode = DUMMY_TAIL.prev;
                removeNode(tailNode);
                cache.remove(tailNode.key);
            }
            
            node = new ListNode(key, value);
            insertAtHead(node);
            cache.put(key, node);
        } else {
            node.value = value;
            moveToHead(node);
        }
    }
    
    public void moveToHead(ListNode p) {
        removeNode(p);
        insertAtHead(p);
    }
    
    private void removeNode(ListNode p) {
        p.next.prev = p.prev;
        p.prev.next = p.next;
    }
    
    private void insertAtHead(ListNode p) {
        ListNode next = DUMMY_HEAD.next;
        
        p.next = next;
        next.prev = p;
        
        DUMMY_HEAD.next = p;
        p.prev = DUMMY_HEAD;
    }
    
    static class ListNode {
        
        int key;
        int value;
        ListNode prev;
        ListNode next;
        
        public ListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
        
    }
    
}

相交链表

找到两个链表的第一个交集的这个 ListNode

  • 的先走 diffListNode
  • 然后一起走,遇到的第一个相同的 ListNode 就是结果
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {   
    int lenA = len(headA);
    int lenB = len(headB);

    if (lenA < lenB) {
        return getIntersectionNode(headB, headA);
    }

    ListNode pA = headA;
    ListNode pB = headB;

    int diff = lenA - lenB;
    while (diff > 0 && pA != null) {
        pA = pA.next;
        diff--;
    }

    while (pA != null && pB != null) {
        if (pA == pB) {
            return pA;
        }

        pA = pA.next;
        pB = pB.next;
    }

    return null;
}

private int len(ListNode root) {
    int count = 0;
    ListNode p = root;

    while (p != null) {
        count++;
        p = p.next;
    }

    return count;
}

K 个一组翻转链表

  • 找到第 kth 个节点
  • 翻转 headkth 之间的节点
  • kth.next 就是新的 newHead,递归翻转 reverseKGroup(newHead)
  • 上次翻转完的 head 变成了尾巴,这个 headnext 要指向新的 reverseKGroup 返回的节点
public ListNode reverseKGroup(ListNode head, int k) {
    ListNode kth = findKth(head, k);
    
    if (kth != null) {
        ListNode newHead = kth.next;

        reverse(head, kth);
        head.next = reverseKGroup(newHead, k);

        return kth;
    }

    return head;
}

// 1,2,3,4,5 k = 3,
// 那么 最终返回的 Node 指向 3
// 如果不够,比如 k = 100,那么返回 null
private ListNode findKth(ListNode head, int k) {
    int count = 1;
    ListNode p = head;

    while (count < k && p != null) {
        p = p.next;
        count++;
    }

    return count == k ? p : null;
}

// 1,2,3 => 3,2,1
private void reverse(ListNode head, ListNode end) {
    ListNode newHead = null;
    ListNode p = head;

    while (p != end) {
        ListNode next = p.next;
        
        p.next = newHead;
        newHead = p;

        p = next;
    }

    end.next = newHead;
}

链表是否有环

设置 fasterslower 指针,相遇即可证明有环。

public boolean hasCycle(ListNode head) {
    if (head == null) {
        return false;
    }

    ListNode slower = head;
    ListNode faster = head.next;

    while (slower != null && faster != null) {
        if (slower == faster) {
            return true;
        }

        slower = slower.next;

        if (faster.next == null) {
            return false;
        }

        faster = faster.next.next;
    }

    return false;
}

链表找到环的入口节点

  • 快慢指针找到相遇节点 meetNode
  • 根据 meetNode 探测环的长度 cycleLen
  • faster 指针先移动 cycleLen
  • fasterslower 一起移动,直到相遇
// 1 -> 2 -> 3 -> 4 -> 1 -> 2 -> 3
//                     ↑_________|
//
// 假设链表长度为 L = 4
// 假设环长度为 C = 3
// 假设相遇时的点,距离环的入口 [逆时针顺序] 长度为 K
//
// 最终相遇:
// - 快指针走了 L + m * C + K 步骤
// - 慢指针走了 L + n * C + K 步骤
//
// L + m * C + K = 2 * (L + n * C + K)
//
// 化简得到 m * C = L + 2n * C + K
// 化简得到 (m - 2n) * C = L + K
// 化简得到 K = (m - 2n) * C - L = n' * C - L
//
// 即 K 是常数
//
// 此时,相遇点 K 的位置是 n' * C - L,它再走 L 步就能到链表入口处
// 而此时慢指针从头开始走,也需要 L 步才能到链表入口处,所以这个是可以找到入口的
//
// 还有就是如下这个代码,faster 从头开始移动 C 个,因为总长度是 L + C 个,所以全程还剩余 L 个
// 慢指针也需要走 L 步,所以还是会相遇
public class LinkedListCycle2 {

    public ListNode detectCycle(ListNode head) {
        // 是否有环
        ListNode meetNode = hasCycle(head);
        if (meetNode == null) {
            return null;
        }

        // 求出环的个数
        int cycleLen = lengthOfCycle(meetNode);

        // 先移动 cycleLen 个
        ListNode faster = head;
        while (cycleLen > 0) {
            faster = faster.next;
            cycleLen--;
        }

        // 一起移动
        ListNode slower = head;
        while (faster != slower) {
            faster = faster.next;
            slower = slower.next;
        }

        return slower;
    }

    public int lengthOfCycle(ListNode meetNode) {
        ListNode p = meetNode.next;
        int c = 1;

        while (p != meetNode) {
            p = p.next;
            c++;
        }

        return c;
    }

    public ListNode hasCycle(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode slower = head;
        ListNode faster = head.next;

        while (slower != null && faster != null) {
            if (slower == faster) {
                return slower;
            }

            slower = slower.next;

            if (faster.next == null) {
                return null;
            }

            faster = faster.next.next;
        }

        return null;
    }

}

合并 K 个有序链表

借助优先队列 PriorityQueue 即可。

public ListNode mergeKLists(List<ListNode> lists) {
    ListNode DUMMY = new ListNode(-1);
    ListNode p = DUMMY;

    PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {

        @Override
        public int compare(ListNode n1, ListNode n2) {
            if (n1.val < n2.val) {
                return -1;
            } else if (n2.val < n1.val) {
                return 1;
            } else {
                return 0;
            }
        }

    });

    for (ListNode node: lists) {
        if (node != null) {
            queue.offer(node);
        }
    }

    while (!queue.isEmpty()) {
        ListNode curr = queue.poll();

        if (curr.next != null) {
            queue.offer(curr.next);
        }

        p.next = curr;
        p = p.next;
    }

    return DUMMY.next;
}

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

要求是一遍扫描。只用一个指针不行,所以得上两个指针。思路

  • 设置虚拟节点 dummyHead 指向 head
  • 设定双指针 pq,初始都指向虚拟节点 dummyHead
  • 移动 q,直到 pq 之间相隔的元素个数为 n
  • 同时移动 pq,直到 q 指向的为 NULL
  • p 的下一个节点指向下下个节点
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode DUMMY = new ListNode();
    DUMMY.next = head;

    ListNode slower = DUMMY;
    ListNode faster = DUMMY;
    for (int i = 0; i < n; i++) {
        faster = faster.next;
    }

    while (faster != null && faster.next != null) {
        slower = slower.next;
        faster = faster.next;
    }

    slower.next = slower.next.next;

    return DUMMY.next;
}

重排链表

寻找链表中点 + 链表右半段逆序 + 合并链表

注意寻找链表中点的写法:while (faster.next != null && faster.next.next != null) { ... }

public void reorderList(ListNode head) {
    ListNode middle = findMiddle(head);

    ListNode rightHalfHead = middle.next;
    middle.next = null;

    ListNode reversedRightHalfHead = reverse(rightHalfHead);
    mergeListNode(head, reversedRightHalfHead);
}

// 1 -> [2] -> 3 -> 4, 返回 2
// 1 -> 2 -> [3] -> 4 -> 5, 返回 3
private ListNode findMiddle(ListNode head) {
    ListNode slower = head;
    ListNode faster = head;

    // 这样写
    while (faster.next != null && faster.next.next != null) {
        slower = slower.next;
        faster = faster.next.next;
    }

    return slower;
}

private ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode p = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

private void mergeListNode(ListNode headA, ListNode headB) {
    // merge headB -> headA
    // 1 -> 2 -> 3
    // 5 -> 4
    while (headA != null && headB != null) {
        ListNode nextA = headA.next;
        ListNode nextB = headB.next;

        headA.next = headB;
        headB.next = nextA;

        headA = nextA;
        headB = nextB;
    }
}

删除排序链表中的重复元素 II

下面算法虽然正确,但是并没有考虑其降序/升序的性质。

  • 当重复元素,下一个元素开始不重复的时候,prev 指针不需要移动,如下图所示。只需要调整 prev.next = p.next 即可
  1 -> 2 -> 2 -> 2 -> 3
prev             p  
  • 当无重复元素,那么 prev 跟着后移即可
1 -> 2 -> 3 -> 4
    prev p [一起后移即可]
         prev  p
  • 我们需要用 hasDuplicated 变量来标识当前 prev 应不应该移动
public ListNode deleteDuplicates(ListNode head) {
    ListNode DUMMY = new ListNode();
    DUMMY.next = head;

    ListNode prev = DUMMY;
    ListNode p = head;
    boolean hasDuplicated = false;

    while (p != null) {
        if (p.next != null) {
            if (p.next.val == p.val) {
                p = p.next;
                hasDuplicated = true;
            } else {
                // prev -> 重复 -> 重复 -> 不重复
                //                 p
                if (hasDuplicated) {
                    prev.next = p.next;
                    hasDuplicated = false;
                } else {
                    prev = p;
                }

                p = p.next;
            }
        } else {
            if (hasDuplicated) {
                prev.next = p.next;
            } else {
                prev.next = p;
            }

            break;
        }
    }

    return DUMMY.next;
}

排序链表

题目要求空间复杂度是 O(1),因此不能使用递归。应该使用 bottom-to-top 版本的归并排序:

TODO

归并排序,如下使用递归版本的实际上空间复杂度并不是 O(1)

  1. 找到链表中点
  2. 左半段递归,中点的 next 置为 null,右半段递归
  3. 左半段、右半段归并
public ListNode sortList(ListNode head) {
    return mergeSort(head);
}

// 归并排序
private ListNode mergeSort(ListNode head){
    // 如果没有结点/只有一个结点,无需排序,直接返回
    if (head == null || head.next == null) {
        return head;
    }

    // 快慢指针找出中位点
    // 1 -> 2 -> 3
    // f
    // p
    ListNode middle = findMiddle(head);

    // 节点断掉
    ListNode middleNext = middle.next;
    middle.next = null;

    // 对左半部分进行归并排序
    ListNode l = mergeSort(head);

    // 对右半部分进行归并排序
    ListNode r = mergeSort(middleNext);

    return mergeList(l, r);
}

// 1 -> [2] -> 3 -> 4, 返回 2
// 1 -> 2 -> [3] -> 4 -> 5, 返回 3
private ListNode findMiddle(ListNode head) {
    ListNode slower = head;
    ListNode faster = head;

    // 这样写
    while (faster.next != null && faster.next.next != null) {
        slower = slower.next;
        faster = faster.next.next;
    }

    return slower;
}

// 合并链表
private ListNode mergeList(ListNode l,ListNode r){
    // 临时头节点
    ListNode tmpHead = new ListNode(-1);
    ListNode p = tmpHead;
    while (l != null && r != null){
        if (l.val < r.val) {
            p.next = l;
            l = l.next;
        } else {
            p.next = r;
            r = r.next;
        }
        
        p = p.next;
    }
    p.next = (l == null) ? r : l;
    return tmpHead.next;
}

快速排序版本,面试官可能会问。快速排序的整体思路:

  1. 将一段链表 [head] -> ... -> [end] 先进行 partitionpivot 选择 [1] -> [2] -> [3] -> [4],那么 pivot 就是 head.next = [2]
  2. quickSort(left)
  3. quickSort(right)
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) 
        return head;
    
    // 没有条件,创造条件。自己添加头节点,最后返回时去掉即可。
    ListNode newHead = new ListNode(-1);
    newHead.next = head;

    return quickSort(newHead, null);
}

// 带头结点的链表快速排序
private ListNode quickSort(ListNode head, ListNode end) {
    // head.next.next == end 1 -> 2 -> 1
    if (head == end || head.next == end || head.next.next == end) 
        return head;

    // 将小于划分点的值存储在临时链表中
    ListNode tmpHead = new ListNode(-1);
    // partition为划分点,p为链表指针,tp为临时链表指针
    ListNode partition = head.next, p = partition, tp = tmpHead;
    
    // 将小于划分点的结点放到临时链表中
    while (p.next != end) {
        if (p.next.val < partition.val) {
            tp.next = p.next;
            tp = tp.next;

            p.next = p.next.next;
        } else {
            p = p.next;
        }
    }

    // 合并临时链表和原链表,将原链表接到临时链表后面即可
    tp.next = head.next;
    
    // 将临时链表插回原链表,注意是插回!(不做这一步在对右半部分处理时就断链了)
    head.next = tmpHead.next;
    
    quickSort(head, partition);
    quickSort(partition, end);

    // 题目要求不带头节点,返回结果时去除
    return head.next;
}