代码随想录算法训练营第三天 | 203.移除链表元素、206.反转链表、707.设计链表

203.移除链表元素

leetcode
文档讲解
视频讲解

考察链表的基本操作，对于单链表的增加和删除节点来说，通常使用虚拟头节点的方式统一操作。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 建立虚拟头节点，并指向头节点
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;

        // 删除节点需要找到被删除节点的前一个节点
        ListNode prev = dummyHead;
        // curr 用于遍历链表
        ListNode curr = head;
        while (curr != null) {
            // 如果 curr 是要删除的节点，删除即可
            if (curr.val == val) {
                prev.next = curr.next;
            } else {
                // 否则 prev 前移
                prev = curr;
            }
            // curr 前移
            curr = curr.next;
        }

        // 虚拟头节点的 next 始终指向链表的头节点
        return dummyHead.next;
    }
}

206.反转链表

leetcode
文档讲解
视频讲解

考察链表的基本操作，即操作当前节点一般需要知道上一个节点，以及保存对下一个节点的引用。

class Solution {
    public ListNode reverseList(ListNode head) {
        // 对上一个节点的引用
        ListNode prev = null;
        // 遍历链表
        ListNode curr = head;

        while (curr != null) {
            // 对下一个节点的引用
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // 返回新链表的头节点
        return prev;
    }
}

这种做法只关注当前节点的反转，只处理当前节点的指针，让其往前指，下一个节点的反转属于下一次循环的范畴，如图：

由此还可以引出递归法。

class Solution {
    public ListNode reverseList(ListNode head) {
        // 初始 prev 为 null，从 head 开始遍历
        return helper(head, null);
    }

    public ListNode helper(ListNode curr, ListNode prev) {
        // 结束条件，curr 到末尾了，返回 prev
        if (curr == null) return prev;
        // 处理当前节点
        ListNode next = curr.next;
        curr.next = prev;
        // 递归处理下一个节点
        return helper(next, curr);
    }
}

可以看到递归法和迭代法是同一个思路，初始条件相同，结束条件相同，每次只处理当前节点，让当前节点反转。

其实还有一个更好想的方法，那就是 头插法，每次将节点在链表头部插入。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode dummyHead = new ListNode();

        while (head != null) {
            // 保存对下一个节点的引用
            ListNode next = head.next;
            head.next = dummyHead.next;
            dummyHead.next = head;
            head = next;
        }

        return dummyHead.next;
    }
}

707.设计链表

class ListNode {
    public int val;
    public ListNode next;

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

class MyLinkedList {
    public ListNode head;
    public int size;

    public MyLinkedList() {
        this.head = null;
        this.size = 0;
    }

    public int get(int index) {
        if (index < 0 || index >= this.size) return -1;

        ListNode curr = this.head;
        while (index > 0) {
            curr = curr.next;
            index--;
        }

        return curr.val;
    }

    public void addAtHead(int val) {
        ListNode node = new ListNode(val);
        node.next = this.head;
        this.head = node;
        // 别忘记
        this.size++;
    }

    public void addAtTail(int val) {
        ListNode node = new ListNode(val);
        if (this.head == null) {
            this.head = node;
        } else {
            ListNode curr = this.head;
            while (curr.next != null) {
                curr = curr.next;
            }
            curr.next = node;
        }
        // 别忘记
        this.size++;
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > this.size) return;

        ListNode prev = null;
        ListNode curr = this.head;
        ListNode node = new ListNode(val);

        while (index > 0) {
            prev = curr;
            curr = curr.next;
            index--;
        }

        node.next = curr;

        if (prev == null) {
            this.head = node;    
        } else {
            prev.next = node;
        }

        // 别忘记
        this.size++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= this.size) return;

        ListNode prev = null;
        ListNode curr = this.head;

        while (index > 0) {
            prev = curr;
            curr = curr.next;
            index--;
        }

        if (prev == null) {
            this.head = curr.next;
        } else {
            prev.next = curr.next;
        }

        // 别忘记
        this.size--;
    }
}