2020-12-09

数据结构和算法

5 分钟读完 (大约 797 个字) 0次访问

链表题技巧

链表题一般都是逻辑问题，空指针处理，很少会有难思考的智力型题目。一般都是一层while循环加上一些指针操作，掌握以下几个技巧，会如鱼得水

//朴实无华的简陋版框架
while(node != null){
    //指针操作逻辑
    node = node.next;
}
//指针操作逻辑

技巧

1. 在前一个节点停下

比如a->b->c，我现在操作到了b，假设操作逻辑要求删除当前节点b，那么也就是a.next = c，发现根本没有指针能获得节点a，因此我们可以在前一个节点停下，所以根据逻辑的需要，先思考是否需要用到前一个节点

while(node.next != b){	//在前一个节点停下
    //指针操作逻辑
    node = node.next;
}
//此时node在a
node.next = node.next.next

2. 虚拟头部

还是a->b->c删除某个节点，还是刚刚那套逻辑，如果我要删的是a，怎么办？你可能会说直接head = a就被“删除”了，不错，但是这样的话得单独判断要删的节点是不是头节点，代码看起来就很啰嗦，所以链表题通常可以使用一个虚拟头节点。什么时候要加呢？也是思考是否需要用到前一个节点，如果需要，那第一个节点必然也需要一个前置节点

1 2	ListNode root = new ListNode(); root.next = head;

用了虚拟头部后，头节点也可以和其他节点一起操作了

记得return root.next而不是head

3. xx.next，判断xx != null

链表题容易空指针，为什么会空指针，一个方法教你永远不空指针：只要代码里面有node.next，那么就判断node != null，如果有node.next.next，那就判断node != null && node.next != null

归根到底，空指针异常是由于null.next造成的

4. 双指针，不行就三指针

研究表明，指针越多，链表题越容易做，双指针不行就三指针，再不行就四指针，n指针秒一切链表题!

像什么前后指针，快慢指针，都是链表题常用的操作

模板

综上所述，模板如下：

public ListNode LinkedList(ListNode head) {
    //虚拟头部和n指针初始位置
    ListNode root = new ListNode(0);
    root.next = head;

    while (pre != null && pre.next != null){
        //指针操作逻辑
        pre = pre.next;
    }

    return root.next;
}

看一题

力扣19

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

不解释，只是看代码结构

public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null) return null;
    //虚拟头部
    ListNode root = new ListNode(0);
    root.next = head;

    //n指针位置准备
    ListNode pre = root, post = root;
    while (n-- != 0) {
        pre = pre.next;
    }

    while (pre != null && pre.next != null){ //while在前一个节点停下
        pre = pre.next;
        post = post.next;
    }
    if (post != null && post.next != null) post.next = post.next.next; //判空
    return root.next;
}

至于本题具体的思路和其他链表类型的题目点击这里

文章

102

分类

14

标签

26

关注我