链表栈队列

  • 链表问题的最优解往往是在空间复杂度上下功夫，就是怎样用最小的空间复杂度
  • 快指针 慢指针

剑指Offer链表题目(9个)：

  • 6 从尾到头打印链表
  • 18 在O(1)时间内删除链表结点
  • 22 链表中倒数第k个结点
  • 23 链表中环的入口结点
  • 24 反转链表
  • 25 合并两个排序的链表
  • 35 复杂链表的复制
  • 36 二叉搜索树与双向链表
  • 52 两个链表的第一个公共结点
  • 68

6 从尾到头打印链表(☆)

6.1 反转链表法（会改变链表结构，询问是否允许修改输入数据）

6.2 借助栈

6.3 递归（不时候链表很长的时候）

easy，过。

18 在O(1)时间内删除链表结点(☆☆)

18.1 顺序法，找到要删除的结点，如下图(b)。时间:O(n)

18.2 O(1)时间复杂度的值覆盖法:

​ image-20200919163944637

​ 假设要删除结点i，把j的值赋值给结点i，删除j(i指向j的next) 。这种时间复杂度O(1) 。

前提待删除结点在链表中。还有对链表只有1个结点 和 要删除的结点是尾结点做分别处理

22 链表中倒数第k个结点(☆☆)

双指针法:p1,p2指向投结点，快指针p1先走k步，后面一起走

public ListNode getKthFromEnd(ListNode head, int k) {
         ListNode p1 = head,p2 = head;
         while(k > 0){
             p1 = p1.next;
             k--;
         }
         while(p1 != null){
             p1 = p1.next;
             p2 = p2.next;
         }   
         return p2;
    }

快指针p1先走k步，后面一起走.

image-20200919171148225

23 链表中环的入口结点(☆☆☆)

双指针法：快指针遍历到null时，则没有环。有环前提下2指针相遇后，快指针回到起点，循环同时往后面走一步，相遇时的结点即为环的入口结点。

记住这个法则就可以，过。

24 链表反转(☆☆☆☆☆字节)

  1. 迭代法

    采用头插法，定义3个指针:旧链表cur,新链表head, 临时指针temp指向cur的next

  2. 递归法

    • 因为最终结果是最后一个结点是反转后的根，我们就要返回根，递归直到最后一个结点，返回head,也就是递归最后1次返回的是最后一个结点
    • 递归到倒第二个结点，让他的后一个结点指向他自己head.next.next = head
    • 因为要求第一个结点的Next为null， 所以再加一句head.nxet = null;
    public ListNode reverseListpublic 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;
    }

25 合并2个有序链表(☆☆☆☆☆字节)

递归去做。

https://leetcode-cn.com/explore/featured/card/top-interview-questions-easy/6/linked-list/44/

递归退出条件，l1空返回l2，l2空返回l1

1.比较l1,l2，值下的就是head

2.递归调用mergeTwoList函数返回给定参数l1,l2合并后链表的头结点。

3.head.next 指向上面返回的

35 复杂链表的复制(☆☆☆)

法一：时间复杂度O(n^2^),空间复杂度O(1)

①复制原始链表上的每个结点，并用next链接起来

②设置每个结点的sibling属性，需要遍历链表，每个结点需要O(n)

法二：时间复杂度O(n)，空间复杂度O(n)

针对第二步优化，空间换时间，要想每个结点sibling的查找 达到O(1)，自然想到哈希表

​ 假设原始链表结点N的sibling指向结点S，那么复制链表N指向S,哈希表保存N,N`

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

步骤①复制原始链表上的每个结点,把N`接在N的后面

​ image-20200919190749711

​ ②设置复制出来的节点的sibling属性

​ image-20200919190850584

​ ③拆分成2个链表:把奇数位置的结点用next连接起来就是原始链表， 把偶数位置的结点用next连接起来就是复制链表。

image-20200919191018557

注 ： 三种方法背住

36 二叉搜索树与双向链表(☆☆☆)

任然采用递归（也写得出来）

  • 将二叉搜索树的左孩子指向前驱，右孩子指向后继，采用中序递归遍历来操作.

  • 把二叉树看成三部分，根，左子树，右子树

  • 把左右子树转换成双链表后和根节点接起来，根节点的前驱指向左子树中序遍历的最后一个结点；

    根节点的后继指向右子树的最小结点，转换右子树前先存起来它的最小结点

注：解决的关键在于把1个大问题分解成几个小问题，然后递归地处理.

private TreeNode convertprivate TreeNode convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null){
            return null;
        }

        //1.转换左子树，返回中序遍历的最后一个结点
        TreeNode lastNode = convert(pRootOfTree.left);

        //根节点的左孩子指向左子树中序遍历的最后一个结点(转换双链表)
        if (lastNode != null){
            lastNode.right = pRootOfTree;
            pRootOfTree.left = lastNode;
        }
        //2-pre把先右子树的最小结点存下来
        TreeNode successorNode = findSuccessorNode(pRootOfTree.right);
        //2.转换右子树
        TreeNode lastNode2 = convert(pRootOfTree.right);

        //根结点的右孩子指向右子树的最小结点(转换双链表)
        pRootOfTree.right = successorNode;
        if (successorNode != null){
            successorNode.left = pRootOfTree;
        }
        //右子树为空，根节点就是中序遍历的最后1个结点,返回它
        if (lastNode2 == null){
            return pRootOfTree;
        }
        //返回以pRootOfTree为根结点的中序遍历的最后一个结点
        return lastNode2;
    }

注: 有点难

52 两个链表的第一个公共结点(☆☆)

多种解法，用O(m+n)的，leetcode有做过2次.

特点：相交后是一条链表

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/

方法一：长链表先走几步
方法二：哈希表法（易理解）,时间复杂度O(m+n),空间复杂度O(m)或O(n)
          基于相交以及后面的部分是一样的，是一条链表，比较引用/地址是否在哈希表中
方法三：双指针法（不易理解，参考题解有图示），时间复杂度O(m+n),空间复杂度O(1)
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}
 这个题跟结点的值val不太有关系，比较的是引用,也就是当指向的是同一个对象时，即为交点

2.回文链表

法一：将值复制到数组中后用双指针法判断是否为回文 时间复杂度：O(n) 空间复杂度：O(n)
法三：时间复杂度：O(n) 空间复杂度：O(1) 快指针，慢指针 额外空间 需修改原结构

  1. 找到前半部分链表的尾节点。
  2. 反转后半部分链表。
  3. 判断是否为回文。
  4. 恢复链表。
  5. 返回结果。

（这个题最优解需要改结构，工程上不会让你这么做，面试上会）

3.打印有序链表的公共部分？(过)

自己练

链表问题的最优解往往是在空间复杂度上下功夫，就是怎样用最小的空间复杂度
笔试过程中：尽快过掉，该用辅助空间就用辅助空间；
面试过程中：尽量时间复杂度O(n),空间复杂度O(1)

4.【题目14 单链表最难】

1)如何判断单链表有环?

  • 用哈希表;
  • 不用哈希表（很玄学，这里有个结论）分别怎么做 (双指针法)
    1. 满指针走一步，快指针走2步（初始都从第一个结点开始走），循环直到快指针=慢指针
    2. 如果快指针为空，也退出循环，返回null
    3. 否则，快指针指向起点，循环快慢指针各走一步，直到2个指针指向同一个结点，那就是第一个入环结点

2)如何判断2个无环单链表相交，并返回交点；

  • 用哈希表;
  • 不用哈希表,记录长度;
  • 不用哈希表，也不用记录长度;

3)如何判断2个有环单链表相交3种情况
4)一个有环和一个无环单链表是否相交：结论–>不相交

队列

特点：先进先出，一端(队尾)插入，一端(队头)删除

应用：

队列的实现：Queue

一般实现 JDK 接口 Queue
入队 boolean enqueue(E) boolean add(E e);
boolean offer(E e);
出队 E dequeue() E remove();
E poll();
取队头 E getFront() E element();
E peek();
获取队列大小 int getSize() int size();//继承自Collection
队列是否为空 boolean isEmpty(); boolean isEmpty();

add和offer有什么区别？

在没有容量限制的队列中，两者一样，LinkedList 中2者实现就是一样的，且永远返回true。

在有容量限制的队列中，建议使用offer，前者抛出IllegalStateException，后者返回false。

数组实现队列：

​ 就是内部用动态数组(可以自己实现) 实现上面几个方法，非常简单。

入队：调用动态数组的addLast方法.

出队：调用动态数组的removeFirst方法

插入O(1)，删除O(n).

数组实现循环队列:

front:指向队首元素

end:指向队尾元素的下一个位置

初始队列中没有元素时，front指向0，end指向0

定义：队列空，front 等于 end

​ 队列满：(tail + 1) % 队列容量c == front ，要留1个空的位置。

插入平摊O(1)，删除平摊O(1).

//1.定义Queue接口，定义5个操作
//2.定义LoopQueue类，1个队头front,1个队尾end,1个数据数组E[] mData,一个队列当前元素个数size
//3.提供无参构造函数和带参（容量）的构造函数，因为要留1个空位表示队列满，因此new 的容量为 capactity + 1
//4.入队时，队列满则扩容，出队时，队列大小为容量的1/4时，缩容到原来的一半


public class LoopQueue<E> implements Queue<E> {
    private E[] mData;
    private int size;
    private int front;
    private int end;

    public LoopQueue() {
        this(10);

    }
    public LoopQueue(int capacity) {
        mData = (E[])new Object[capacity + 1];
        front = 0;
        end = 0;
        size = 0;
    }

    @Override
    public E poll() {
        if (isEmpty()){
            throw new IllegalArgumentException("the queue is empty");
        }
        E ret = mData[front];
        mData[front] = null;
        front = (front + 1) % mData.length;
        size--;
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0){
            resize(getCapacity() / 2);
        }
        return ret;
    }

    @Override
    public boolean offer(E e) {
        //队列满
        if(front == (end + 1) % mData.length){
            //扩容
            resize(getCapacity() * 2);
        }
        mData[end] = e;
        end = (end + 1) % mData.length;
        size++;
        return true;
    }

    private void resize(int capactity) {
        E[] newObjects = (E[])new Object[capactity + 1];
        for (int i = 0; i < size; i++) {
            newObjects[i] = mData[(front + i) % mData.length];
        }
        mData = newObjects;
        front = 0;
        end = size;
    }

    public int getCapacity(){
        return mData.length - 1;
    }
    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == end;
    }

    @Override
    public E peek() {
        return mData[front];
    }

    @Override
    public String toString() {
        return "LoopQueue{" +
                "mData=" + Arrays.toString(mData) +
                ", size=" + size +
                ", front=" + front +
                ", end=" + end +
                '}';
    }
}
剑指offer leetcode
剑指offer leetcode

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！