数据结构小记｜Wavy's blog

【声明】图源：牛客网

基本概念

链表和数组都是一种线性结构
- 数组是一段连续的存储空间
- 链表空间不一定保证连续，为临时分配的
链表的分类
- 按连接方向分类
  - 单链表
  - 双链表
- 按有环和无环分类
  - 普通链表
  - 循环链表（首尾相接）

链表问题代码实现的关键点
- 链表调整函数的返回值类型，根据要求往往是节点类型
- 处理链表过程中，先采用画图的方式理清逻辑
- 链表问题对于边界条件讨论要求严格（头节点、尾节点、空节点）
链表插入和删除的注意事项
- 特殊处理链表为空，或者链表长度为1的情况
- 注意插入操作的调整过程（找到插入位置的前一个节点和后一个节点）
- 注意删除操作的调整过程
- 注意在删除或插入节点时，头尾节点及空节点需要特殊考虑
  - 双链表的插入与删除和单链表类似，但是需要额外考虑previous指针的指向
单链表翻转操作的注意事项
- 当链表为空或者长度为1时，特殊处理

经典案例

案例一

题目

环形链表插值

给定一个整数num，如何在节点值有序的环形链表中插入一个节点值为num的节点，并且保证这个环形单链表依然有序。

分析

时间复杂度O(n)，空间复杂度O(1)

首先生成节点值为num的新节点
如果原链表为空，让node自己形成环形链表，返回node即可
如果链表不为空，令变量previous(p)等于头节点(head)，变量current(c)等于第二个节点，然后令p和c同步移动下去：
- 如果p.val<=node.val并且c.val>=node.val，则将node插入到p和c之间，返回head即可
- 举例演示
如果p和c转一圈都没有发现应该插入的位置，此时node应该插入头节点的前面，情况如下
- node节点的值比链表中的每个节点的值都大，此时返回head
- node节点的值比链表中的每个节点的值都小，此时应返回node作为环形链表的新头部（保证有序）

实现

/**
 * 有一个整数val，如何在节点值有序的环形链表中插入一个节点值为val的节点，并且保证这个环形单链表依然有序。
 * 给定链表的信息，及元素的值A及对应的nxt指向的元素编号同时给定val，请构造出这个环形链表，并插入该值。
 * 测试样例：
 * [1,3,4,5,7],[1,2,3,4,0],2
 * 返回：{1,2,3,4,5,7}
 */
class ListNode{
    int val;
    ListNode next=null;
    ListNode(int val){
        this.val = val;
    }
}
public class InsertValue {
    public ListNode insert(int[] A, int[] nxt, int val) {
        if(A == null){
            ListNode node = new ListNode(val);
            return node;
        }
        ListNode head = new ListNode(A[0]); // 头节点
        ListNode tail = head;
        for(int i=0;i<A.length-1;i++){
            tail.next = new ListNode(A[nxt[i]]);
            tail = tail.next;
        }

        show(head);

        ListNode node = new ListNode(val);
        // 如果val比头节点的值还小，则将其插入到头节点之前并作为头节点返回
        if(val<head.val){
            node.next = head;
            tail.next = node;
            return node;
        }

        ListNode pre = head;
        ListNode cur = head.next;
        while(cur!=null){
            if(val>=pre.val && val<=cur.val){
                node.next = cur;
                pre.next = node;
                return head;
            }
            pre = cur;
            cur = cur.next;
        }
        // 如果node是最大的
        node.next = null;
        pre.next = node;

        return head;
    }

    // 输出链表
    public void show(ListNode head){
        ListNode p = head;
        while(p!=null){
            System.out.print(p.val+"->");
            p = p.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        InsertValue obj = new InsertValue();
        int[] A = {1,3,4,5,7};
        int[] nxt = {1,2,3,4,0};
        int val = 4;
        ListNode head = obj.insert(A,nxt,val);
        obj.show(head);
    }

}

案例二

题目

访问单个节点的删除

给定一个链表中的节点node，但不给定整个链表的头节点。如何在链表中删除node？请实现这个函数，要求时间复杂度为O(1)。

分析

常见解法

将待删除节点的下一个节点的值拷贝给当前节点，之后删除下一个节点。

存在问题

无法删除最后一个节点。因为没有下一个节点的值可以拷贝给当前节点。也不能将待删除节点在内存中的区域设置成null，因为null在系统中是一个特定的区域如果想让待删除节点的上一个节点指向null，必须找到该节点才行。因此这种删除方式并不是删除了该删除的节点，而是进行了值的拷贝。

在实际生产中，这种方法并不可行，比如：

节点结构复杂且拷贝操作受限时
在工程上会影响外部依赖

实现

/**
 * 实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。
 * 给定待删除的头节点和要删除的数字，请执行删除操作，返回删除后的头结点。链表中没有重复数字
 */
public class Remove {
    // 删除指定节点
    public ListNode removeNode(ListNode pNode, int delVal) {
        // 定义辅助头节点
        ListNode dummy = new ListNode(-1);
        dummy.next = pNode;
        ListNode pre = dummy;
        ListNode cur = dummy.next;
        while(cur!=null){
            if(cur.val == delVal){
                pre.next = cur.next;
                break;
            }
            pre = cur;
            cur = cur.next;
        }
        return dummy.next;
    }
}

案例三

题目

链表的分化

给定一个链表的头节点head，再给定一个数num，请把链表调节成节点值小于num的节点都放在链表的左边，值等于num的节点都放在链表的中间，值大于num的节点，都放在链表的右边。

分析

简单做法：（使用了额外的结构）

将链表的所有节点放入到数组中，然后将数组进行快排划分的调整过程。（类似荷兰国旗问题）
然后将数组中的节点依次重新串连

最优解法：

在遍历链表的过程中，将链表分成小于num的链表，等于num的链表和大于num的链表
最后再将这三个链表整体的连接起来

实现

public ListNode listDivide(ListNode head, int val) {
    ListNode smallHead = null; // <=
    ListNode smallTail = null;
    ListNode bigHead = null;   // >
    ListNode bigTail = null;
    ListNode next = head;
    while(head!=null){
        next = head.next;
        head.next = null;  // 断开连接
        if(head.val <= val){
            if(smallHead==null){
                smallHead = head;
                smallTail = head;
            }else{
                smallTail.next = head;
                smallTail = smallTail.next;
            }
        }else{
            if(bigHead==null){
                bigHead = head;
                bigTail = head;
            }else {
                bigTail.next = head;
                bigTail = bigTail.next;
            }
        }
        head = next;
    }
    if(smallHead!=null)
        smallTail.next = bigHead;
    return smallHead==null?bigHead:smallHead;
}

案例四

题目

打印两个链表的公共值

给定两个有序链表的头节点head1和head2，打印两个有序链表的公共部分。

分析

如果两个链表有任何一个为空，直接返回即可。
如果两个链表均不为空，则继续按照下面的步骤进行处理：
- 从两个链表的头节点开始遍历，如果list1当前节点值小于list2当前节点值，则继续遍历list1的下一个节点。
- 如果list2的当前节点值小于list1的当前节点值，则继续遍历list2的下一个节点。
- 如果两个链表的当前节点值相等，则都打印当前节点值，同时向下一个节点移动。
- list1和list2有一个遍历到null，则整个过程停止。
演示如下

实现

public int[] findCommonParts(ListNode headA, ListNode headB) {
    if(headA == null || headB == null)
        return null;
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    ListNode p = headA;
    ListNode q = headB;
    while(p!=null && q!=null){
        if(p.val == q.val) {
            tmp.add(p.val);
            p = p.next;
            q = q.next;
        }
        else if(p.val < q.val)
            p = p.next;
        else
            q = q.next;
    }
    int[] res = new int[tmp.size()];
    for(int i=0;i<tmp.size();i++)
        res[i] = tmp.get(i);
    return res;
}

案例五

题目

链表的K逆序

给定一个单链表的头节点head，实现一个调整单链表的函数，使得每K个节点之间逆序，如果最后不够K个节点一组，则不调整最后几个节点。

举例：

1->2->3->4->5->6->7->8->null，K=3

调整后为

3->2->1->6->5->4->7->8->null

因为K=3，所以每三个节点之间逆序，但其中的7,8不调整，因为只有两个节点不够一组

分析

如果链表为空，或长度为1，或K<2，链表不用进行调整
方法一：时间复杂度O(n)，额外空间复杂度O(k)（利用栈进行处理）
- 元素依次进栈，在栈中凑齐K个元素就依次从栈中弹出，栈中弹出的顺序是原来顺序的逆序，所以这K个元素之间就实现了逆序。
- 下一组元素继续按照这个过程处理，直到完成要求。
- 实现过程中需要注意的地方：
  - 最后节点数不足K个应该如何处理？
  - next指针重连如何处理？
  - 逆序后的每组子链表之间如何连接？
  - 第一组元素的特殊处理？
  - 调整后头节点被改变如何处理？

方法二：时间复杂度O(n)，额外空间复杂度O(1)（省去了栈的辅助）
- 记录下每组的第一个节点
- 往下遍历到K个节点时，就从第一个节点开始做逆序调整
- 把每组逆序之后的头节点和上一组已经调整好的尾节点相连

实现

public ListNode inverse(ListNode head, int k) {
    if(head == null || k<2)
        return head;
    ListNode cur = head;
    int count = 0;
    while(cur!=null && count<k){
        cur = cur.next;
        count++;
    }
    if(count==k){
        // 下一组翻转内容头节点
        cur = inverse(cur,k);
        while(count-->0){
            ListNode tmp = head.next; // 翻转
            head.next = cur;
            cur = head;  // 向下遍历
            head = tmp;
        }
        head = cur; // 翻转后的头节点
    }
    return head;
}

案例六

题目

链表指定值清除

给定一个单链表的头节点head，链表中每个节点保存一个整数，再给定一个值val，把所有等于val的节点删掉。

分析

把整个过程看做一个构造链表的过程，假设之前构造的链表头是head，尾是tail。
如果当前节点now.val == val，就直接抛弃该节点；否则就将该节点接到之前链表的末尾。接到末尾需要改变末尾的next指针，让其指向now节点，并将now节点设置成新的尾节点。
特殊情况
- 最初将head和tail等于null，所以第一个接上的节点既是head也是tail
- 接入第一个节点，tail是没有next指针的
演示如下

实现

public ListNode clear(ListNode head, int val) {
    ListNode nHead = null;  // 新链表
    ListNode nTail = null;
    ListNode cur = null;
    while(head!=null){
        cur = head.next;
        head.next = null;   // 与原链表断开
        if(head.val!=val){
            if(nHead==null){ // 新链表还没节点
                nHead = head;
                nTail = head;
            }else{
                nTail.next = head;
                nTail = nTail.next;
            }
        }
        head = cur;
    }
    return nHead;
}

案例七

题目

链表的回文结构

判断一个链表是否是回文结构

例如：

1->2->3->2->1，是回文结构，返回true

1->2->3->1，不是回文结构，返回false

分析

方法一：时间复杂度O(n)，使用了n的额外空间

申请一个栈结构，在遍历链表的过程中将元素依次入栈
此时栈顶到栈底的元素顺序就是链表中元素顺序的逆序
再次遍历链表，同时栈向外弹出节点。比对遍历节点和弹出节点的值是否一样，如果每一步节点都相等，说明链表是回文结构。否则不是回文结构。
演示过程

方法二：时间复杂度O(n)，使用了n/2的额外空间（快慢指针，折半比较）

申请一个栈结构，在遍历链表的过程中将元素依次入栈，与方法一不同的是这次是用快慢两个指针同时遍历，快指针一次两步，慢指针一次一步。
慢指针遍历时将指针压入栈中。当快指针走完时，慢指针会来到链表的中间位置。
栈顶到栈底的顺序是链表左部分的逆序。
此时链表长度如果为奇数，就不把中间的节点压入栈中
接下来慢指针继续遍历，同时栈弹出节点。对比两个值是否相等，如果每一步节点都相等，说明链表是回文结构。否则不是回文结构。
演示过程

方法三：时间复杂度O(n)，使用的额外空间复杂度O(1)（最优解）

找到链表的中间节点（快慢指针）
将链表的后半部分做逆序调整
从链表的两端开始，依次对比节点值是否一样。如果对比到中间位置是一样的，则说明链表是回文结构，否则不是。
无论是否是回文结构，返回之前，需要把链表的结构调整回原样，之后才可以返回结果。
演示过程

实现

public boolean isPalindrome(ListNode pHead) {
    ListNode slow = pHead;
    ListNode fast = pHead;
    // 找到链表的中点
    while(fast!=null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;
    }
    // 翻转链表后半部分
    ListNode p = null;
    while(slow!=null){
        ListNode tmp = slow.next;
        slow.next = p;
        p = slow;
        slow = tmp;
    }
    ListNode cur = pHead;
    // 判断是否回文
    while(p!=null){
        if(p.val == cur.val){
            p = p.next;
            cur = cur.next;
        }else{
            return false;
        }
    }
    return true;
}

案例八

题目

复杂链表的复制

一个链表结构中，每个节点不仅包含有一条指向下一个节点的next指针，同时含有一条rand指针，rand指针可能指向任何一个链表中的节点，请复制这种含有rand指针节点的链表。

分析

链表长度为0或者为空，直接返回null。
遍历链表，拷贝当前节点，将拷贝节点放在当前节点和下一个节点之间。
再次遍历链表，同时访问当前节点和它的拷贝节点，以1为例，通过1的rand指针可以找到3，那么1’的rand指针可以成功的找到3的拷贝节点3’。
其他节点操作同步骤三。
将原链表和拷贝链表分离即可。返回拷贝链表，同时原链表也未发生改变。
过程演示

实现

class RandomListNode{
    int val;
    RandomListNode next = null;
    RandomListNode random = null;
    RandomListNode(int val){
        this.val = val;
    }
}
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead == null)
            return pHead;
        // 复制链表的每个节点
        RandomListNode current = pHead;
        RandomListNode pNext = null;
        while(current!=null){
            pNext = current.next;
            current.next = new RandomListNode(current.val);
            current.next.next = pNext;
            current = pNext;
        }

        // 遍历链表复制rand指针
        current = pHead;
        RandomListNode copyCur = null;
        while(current!=null){
            pNext = current.next.next;
            copyCur = current.next;
            copyCur.random = current.random != null?current.random.next:null;
            current = pNext;
        }
        // 将两个链表拆分
        RandomListNode copyHead = pHead.next;
        current = pHead;
        while(current!=null){
            pNext = current.next.next;
            copyCur = current.next;
            current.next = pNext;
            copyCur.next = pNext != null?pNext.next:null;
            current = pNext;
        }
        return copyHead;
    }
}

案例九

题目

链表判环

如何判断一个单链表是否有环？有环的话返回进入环的第一个节点，无环的话返回空。如果链表的长度为N，请做到时间复杂度O(N)，额外空间复杂度O(1)

分析

普通解法利用哈希表来实现（受额外空间复杂度限制）
- 遍历链表，每遍历一个节点就在哈希表中进行记录。
- 如果一个链表无环，则直到遍历结束时也不会出现重复的节点。此时返回空。
- 如果一个链表有环，根据哈希表肯定会有遍历到同一个节点的情况。第一个重复的节点肯定是第一个进入环的节点。直接返回即可。
符合题目要求解法：快慢指针
- 利用快慢两个指针进行遍历，快指针一次走两步，慢指针一次走一步。
- 如果链表无环，则快指针会迅速发现链表末尾为空的位置。返回空即可。
- 如果链表有环，则快指针和慢指针会在链表中的某个位置相遇。
- 在相遇时刻，让快指针从链表的头部开始重新遍历，一次走一步，同时慢指针继续往下走，一次也走一步。
- 当快慢指针再次相遇时，相遇节点即进入环的第一个节点。

实现

public int chkLoop(ListNode head) {
    if(head == null || head.next == null)
        return -1;
    ListNode slow = head;
    ListNode fast = head;
    while(fast!=null && fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;
        if(slow == fast)
            break;
    }
    if(slow == fast){
        fast = head;
        while(fast!=slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
    return -1;
}

案例十

题目

无环单链表判断相交

如何判断两个无环单链表是否相交？相交的话返回第一个相交的节点，不相交的话返回空。如果两个链表长度分别为N和M，请做到时间复杂度O(N+M)，额外空间复杂度O(1)。

分析

普通方法用哈希表来实现（受额外空间复杂度限制）
- 先遍历第一个链表，将第一个链表的节点都存入哈希表中。
- 遍历第二个链表，在遍历的过程中一旦遇到某个节点在哈希表中有记录，则说明这个节点在第一个链表中也存在，并且是它们第一个相交的节点。如果第二个链表遍历完了，未出现上述情况，则说明两个链表不相交。
符合题目要求的解法：
- 遍历两个链表，统计两个链表各自的长度。假设一个链表长100，另一个长50。
- 先让长为100的链表走50步，之后两个链表再一起往下遍历。
- 如果两个链表相交的话，它们在共同走的过程中会到达第一个相交的节点。
- 如果走到最后都没有相交，返回空。

实现

class ListNode{
    int val;
    ListNode next=null;
    ListNode(int val){
        this.val = val;
    }
}
public boolean chkIntersect(ListNode headA, ListNode headB) {
    if(headA == null || headB == null)
        return false;
    ListNode pA = headA;
    ListNode pB = headB;
    int lenA = 0;
    int lenB = 0;
    while (pA!=null){
        lenA++;
        pA = pA.next;
    }
    while (pB!=null){
        lenB++;
        pB = pB.next;
    }
    int tmp = (lenA-lenB)>0?lenA-lenB:lenB-lenA;
    if(lenA>lenB){
        pA = headA;
        while(tmp-->0){
            pA = pA.next;
        }
    }else {
        pB = headB;
        while(tmp-->0){
            pB = pB.next;
        }
    }
    while(pA!=null && pB!=null){
        if(pA == pB)
            return true;
        pA = pA.next;
        pB = pB.next;
    }
    return false;
}

案例十一

题目

有环单链表相交判断

如何判断两个有环单链表是否相交？相交的话返回第一个相交的节点，不相交的话返回空。如果两个链表长度分别为N和M，请做到时间复杂度O(M+N)，额外空间复杂度O(1)。

分析

根据之前介绍的找到环形单链表第一个入环的方法，分别找到两个链表各自的入环节点。
两个链表的入环节点是同一个节点的情况：
- 如果两个入环节点是同一个节点，则两个链表相交。
- 要找到两个有环单链表相交的第一个节点，思路和求两个无环单链表相交的情况类似。仅是终止位置不同，但找的逻辑相同。在本题中，以共用的入环节点作为终止位置。

两个链表的入环节点不是同一个节点的情况：
- 有两种拓扑结构，如何区分是哪种拓扑结构呢？
  - 从第一个链表的入环节点开始往下遍历，如果能够回到原来的出发位置，说明是结构一。这种情况下，直接返回空即可。（两个链表不相交）
  - 如果在回到原来的位置之前，遇到了第二个链表的入环节点，说明是结构二。这种情况下，返回链表1或链表2的入环节点都可以，两者都是两个链表第一次相交的节点，只不过前者离链表1近，后者离链表2近。

实现

public class ChkIntersection {
    public boolean chkInter(ListNode head1, ListNode head2) {
        // write code here
        // 分别找到两个链表的入环节点
        ListNode p1 = find(head1);
        ListNode p2 = find(head2);
        if(p1 == p2)
            return true;
        // 两个链表的入环节点不是同一个
        ListNode cur = p1.next;
        while(cur!=p1){
            if(cur == p2) // 如果遇到另一个链表的入环节点
                return true;
            cur = cur.next;
        }
        return false;
    }
    // 查找入环节点
    public ListNode find(ListNode head){
        if(head == null)
            return null;
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast)
                break;
        }
        if(slow == fast){
            fast = head;
            while(fast!=slow){
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
        return null;
    }
}

案例十二

题目

单链表相交判断

给定两个单链表的头节点head1和head2，如何判断两个链表是否相交？相交的话返回第一个相交的节点，不相交的话返回空。

分析

找到两个链表各自的入环节点。假设：
- head1的链表入环节点为node1
- head2的链表入环节点为node2
如果node1和node2，一个为空，另一个不为空，则两个链表不可能相交。
如果node1和node2都等于空，说明两个链表都无环，则可以采用案例十中的无环单链表求交的方法进行处理。
如果node1和node2都不为空，说明两个链表都有环，则可以采用案例十一的方法进行后续解答。

实现

public class ChkIntersection {
    public boolean chkInter(ListNode head1, ListNode head2, int adjust0, int adjust1) {
        // write code here
        ListNode p1 = find(head1);
        ListNode p2 = find(head2);
        
        if(p1!=null && p2!=null){// 都有环的情况
            return chkInterCircle(head1,head2);
        }else if(p1==null && p2==null){// 都没有环的情况
            return chkInterNotCircle(head1,head2);
        }else{
            return false;
        }
    }
    // 没有环情况下
    public boolean chkInterNotCircle(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)
            return false;
        ListNode pA = headA;
        ListNode pB = headB;
        int lenA = 0;
        int lenB = 0;
        while (pA!=null){
            lenA++;
            pA = pA.next;
        }
        while (pB!=null){
            lenB++;
            pB = pB.next;
        }
        int tmp = (lenA-lenB)>0?lenA-lenB:lenB-lenA;
        if(lenA>lenB){
            pA = headA;
            while(tmp-->0){
                pA = pA.next;
            }
        }else {
            pB = headB;
            while(tmp-->0){
                pB = pB.next;
            }
        }
        while(pA!=null && pB!=null){
            if(pA == pB)
                return true;
            pA = pA.next;
            pB = pB.next;
        }
        return false;
    }
    // 有环情况下
    public boolean chkInterCircle(ListNode head1, ListNode head2) {
        // write code here
        // 分别找到两个链表的入环节点
        ListNode p1 = find(head1);
        ListNode p2 = find(head2);
        if(p1 == p2)
            return true;
        // 两个链表的入环节点不是同一个
        ListNode cur = p1.next;
        while(cur!=p1){
            if(cur == p2) // 如果遇到另一个链表的入环节点
                return true;
            cur = cur.next;
        }
        return false;
    }
    // 查找入环节点
    public ListNode find(ListNode head){
        if(head == null)
            return null;
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast)
                break;
        }
        if(slow == fast){
            fast = head;
            while(fast!=slow){
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
        return null;
    }
}