递归移除链表元素、翻转链表(leetcode easy 203、206)、设计链表(leetcode medium 707)

移除链表元素

题目链接: https://leetcode.cn/problems/remove-linked-list-elements/

思路:

• 主要考虑移除元素后需要让被移除元素前置节点的next指向其后置节点, 采用递归法可以很方便的解决. 递归法遍历到末尾后依次将当前头节点返回给上一层, 如果当前元素是需要被删除的元素则将当前元素的next节点作为头节点返回.

代码(java):

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;  //递归终止
        head.next = removeElements(head.next, val); //替换删除后链表
        return head.val != val ? head : head.next;  //删除操作
    }
}

翻转链表:

题目链接: https://leetcode.cn/problems/reverse-linked-list/

思路:

• 递归到链表末尾将链表末尾元素作为新的头节点返回, 并在递归返回的过程中进行翻转操作.

注意事项:

1. 返回过程中每层递归返回的都是新的头节点, 即原链表的末尾元素.
2. 递归返回过程中, 翻转操作可以通过当前层的head.next节点的next节点指向当前层head实现.
3. 每层翻转完成后需要将当前节点的next置为null, 否则会在新链表的末尾形成循环链表.

代码:

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;  //保证当前层节点作为头节点的子链表长度>=2, 作为递归终止条件
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

设计链表:

题目链接: https://leetcode.cn/problems/design-linked-list/

思路(单向链表):

• 使用一个Node类用于记录链表数据, MyLinkedList只保存链表的头节点, 在MyLinkedList内维护一个变量size记录链表长度用于提高链表操作效率.

代码(java):

class MyLinkedList {
    Node head;
    int size = 0;

    public MyLinkedList() {
    }

    /*根据索引获取元素*/
    public int get(int index) {
        if (index >= size || size == 0) {
            return -1;
        }
        Node temp = head;
        while (index-- > 0) {
            temp = temp.next;
        }
        return temp.val;
    }

    /*在头部添加元素*/
    public void addAtHead(int val) {
        this.head = new Node(val, head);
        size++;
    }

    /*在尾部添加元素*/
    public void addAtTail(int val) {
        if (size == 0) {
            addAtHead(val);
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new Node(val, null);
        size++;
    }

    /*在指定索引处添加元素*/
    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        if (index <= 0) {
            addAtHead(val);
            return;
        }
        Node temp = head;
        while (index-- > 1) {
            temp = temp.next;
        }
        temp.next = new Node(val, temp.next);
        size++;
    }

    /*删除指定索引处元素*/
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        if (index == 0) {
            head = head.next;
        } else {
            Node temp = head;
            while (index-- > 1) {
                temp = temp.next;
            }
            temp.next = temp.next.next;
        }
        size--;
    }
}

static class Node {
    int val;
    Node next;

    Node() {}

    Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }
}