526互联

day 3 链表 203.移除链表元素、707.设计链表、206.反转链表

发布时间 2023-10-27 18:58:02作者: 钵钵鸡不是鸡

203.移除链表元素

题目链接：203.移除链表元素

视频教程

文字教程

虚拟头节点

虚拟头节点的目的：消除头节点的特殊性

  • 痛点：删除头节点和删除其他节点的操作是不一样的，导致写代码时需要分两种情况考虑
    • 因为其他链表都是通过前一个节点删除的
    • 而头节点没有前一个节点，只需将头节点向后移动一位即可删除

因此为了进一步优化，可以用一种统一的逻辑来删除所有节点，就必须使所有节点 (特指头节点) 都拥有前一个节点

所有节点都拥有前一个节点可以保证头节点和其他节点删除的逻辑保持一致 （这里有点啰嗦，但这点很重要，理解了这点就能理解为什么虚拟头节点这么好使了）

来用这张图看一看如何使用虚拟头节点。

这里来给链表添加一个虚拟头节点成为新的头节点，此时要移除这个旧的头节点 1 。

这里是不是就可以将删除头节点和删除其他节点的方式统一了

代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(); // 设置虚拟头节点
        dummyHead.next = head; // 虚拟头节点的next指向head
        ListNode cur = dummyHead; // 利用cur遍历链表
        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next; // 删除 val==target 的节点，并cur.next指向下一个节点 
            } else {
                cur = cur.next; // cur指向下一个节点
            }
        }
        return dummyHead.next; // 这里返回真正的头节点
    }
}

707.设计链表

题目链接：707.设计链表

视频教程

文字教程

思路

  • 这道题涉及了五个接口的实现：

    • 获取链表第Index个节点的数值

    • 在链表的最前面插入一个节点

    • 在链表的最后面插入一个节点

    • 在链表第index个节点前面插入一个节点

    • 删除链表的第index个节点

  • 核心思路：在链表中寻找特定位置的节点 cur

    核心代码：(本人只提供其中一种方式)

    cur = head; // cur 指向头节点
for(int i = 0;i < index;i++) {
    cur = cur.next;
}

    for(int i = 0;i < index;i++) 说明：

    • 这段代码中的 < 可以换为 <= ，根据条件而定
    • 这段代码中的 index 可以换位 size ，根据条件而定

代码实现

纠正一点我之前的错误，Java不允许用 int 作为 boolean 使用

错误代码，仅供批斗：

while (index--) {   // 报错信息：int cannot be converted to boolean
    cur = cur.next;
}

正确代码：

注意中间多次设计链表的循环，循环条件和 cur 的赋值是什么容易错误的点

class ListNode {

    int val;

    ListNode next;

    public ListNode() {

    };

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

class MyLinkedList {

    ListNode head;

    int size;

    public MyLinkedList() {
        head = new ListNode(0);
        size = 0;
    }
    
    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode cur = head; 
        for (int i = 0;i <= index;i++) { // 这个利用index循环找位置的技巧很常用, 循环条件要注意
            cur = cur.next;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        ListNode node = new ListNode(val);
        node.next = head.next;
        head.next = node;
        size++;
    }
    
    public void addAtTail(int val) {
        ListNode node = new ListNode(val);
        ListNode cur = head;
        for (int i = 0;i < size;i++) { 
            cur = cur.next;
        }
        cur.next = node;
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        } else if (index == size) {
            addAtTail(val);
        } else if (index < 0) {
            addAtHead(val);
        } else {
            ListNode node = new ListNode(val);
            ListNode cur = head;
            for (int i = 0;i < index;i++) { 
                cur = cur.next; // 找到添加位置的前一个节点
            }
            node.next = cur.next;
            cur.next = node;
            size++;
        }
    }
    
    public void deleteAtIndex(int index) {
        if (index >= 0 && index < size) {
            ListNode cur = head;
            for (int i = 0;i < index;i++) {
                cur = cur.next; // 找到删除位置的前一个节点
            }
            cur.next = cur.next.next;
            size--;
        }
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

206.反转链表

题目链接： 206.反转链表

视频教程

文字教程

思路

本题只需要改变链表的next指针的指向，直接将链表反转，实现时间复杂度：O(n) 空间复杂度：O(1)，如图所示：

  • 双指针的实现思路：利用前后指针在遍历链表的同时改变指针next

    利用双指针实现反转链表的过程：（纠正：动画应该是先移动pre，在移动cur）

  • 实现过程：

    • 首先定义两个指针，一个是 cur 指向head，一个是 pre 初始化为 null

    • 再定义一个临时存储节点，每次循环要先把 cur.next 节点用tmp保存起来（原因可以看代码实现里的注释）

    • 循环条件要设定为 cur==null ，因为只有 cur 通过循环条件才能转向 next

    • 循环体：

      tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;

    • return 时要返回 pre ，此时 pre 指向反转后的头节点，cur 指向 null

代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head; // 遍历链表的当前节点
        ListNode pre = null; // 遍历链表的前一个节点
        ListNode tmp; // 临时存储cur节点的下一个节点
        while (cur != null) { // 循环条件中可以通过哪些节点，哪些节点的next才会被反转
            tmp = cur.next; // 临时节点先存储cur的下一个节点，因为下面cur.next要指向pre
            cur.next = pre; // cur.next指向pre
            pre = cur; // pre指向下一个节点
            cur = tmp; // cur指向下一个节点 
        }
        return pre;
    }
}