代码随想录第三天|链表设计、迭代和递归网站首页 技术教程

代码随想录第三天|链表设计、迭代和递归

非科班小白宋宋 2023-06-01 20:00:02

简介代码随想录第三天|链表设计、迭代和递归

代码随想录第三天|

Leetcode 203 移除链表元素

题目链接: 移除链表元素
自己的思路:使用迭代法进行处理。定义一个临时变量cur进行链表的遍历，在遍历过程中，要判断当前结点cur的下一个结点的值是否为val，如果为val的话，进行删除操作，即cur.next=cur.next.next，把中间结点删除；如果值不为val的话，cur前进一步，即cur=cur.next，直到遍历完整个链表。这里要注意的是，头结点是否为空或者值是否为val的考虑，因为头结点前面并没有结点，所以无法对头结点删除，所以这里我们设置一个虚拟头结点dummyhead，将它初始化为任何数，并且指向头结点head，这样就可以避免以上考虑，迭代的终止条件是cur.next!=null，因为在迭代的过程中会出现cur.next.next，要避免出现空指针的情况。最后返回虚拟头结点的下一个结点即可。由于对递归不是很熟悉，所以第一时间没有想到用递归来做，还是要多刷一些题加深对递归的理解。
正确思路:迭代或者递归

迭代代码:

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //定义一个虚拟头结点，这样可以避免考虑头结点为NULL或者为val的情况
        ListNode dummyhead = new ListNode(0,head);
        //定义一个临时变量用来遍历链表进行删除操作
        ListNode cur = dummyhead;
        //因为下面会有cur.next.next所以这里cur.next不可以为null
        while(cur.next!=null){
            //如果cur下一个结点的值为val
            if (cur.next.val==val){
                //删除操作
                cur.next = cur.next.next;
            }else{
                //如果下一个节点值不为val则结点前进
                cur = cur.next;
            }
        }
        //返回虚拟头结点的下一个结点
        return dummyhead.next;
    }
}

复杂度分析：
时间复杂度： $O (n)$
空间复杂度： $O (1)$

递归分析：刚开始学递归，所以最好把整个递归的过程都弄明白才好进行后面树的递归学习。将当前的链表依次缩小为非常小的链表，然后通过归来生成新的链表
递归终止条件：当输入当前结点head为空的时候，向上返回
递归参数：当前结点以及需要删除的结点值val
单层递归：使用递归函数向下递归，得到head的下一个结点，如果结点值为val，则返回当前结点的下一个结点，否则返回当前结点

递归过程：以链表1–>2–>3–>4–>3–>5–>null为例 val=3
递操作就不用说了，从1开始一直递到null为止
执行单层归操作：
当在结点值为5的时候，返回null，当前的head为5结点，那么head.next=null，构造子链表为5–>null，返回上一层；
当在结点值为3的时候，判断下一个结点的值是否为val，5 $\neq =$ 3，所以返回head.next为5所在的结点，构造子链表3–>5–>null，返回上一层；
当在结点值为4的时候，判断下一个结点的值是否为val，3 $=$ 3，所以返回head.next为5所在的结点，构造子链表4–>5–>null，返回上一层；
当在结点值为3的时候，判断下一个结点的值是否为val，4 $\neq =$ 3，所以返回head.next为4所在的结点，构造子链表3–>4–>5–>null，返回上一层；
当在结点值为2的时候，判断下一个结点的值是否为val，3 $=$ 3，所以返回head.next为4所在的结点，构造子链表2–>4–>5–>null，返回上一层；
当在结点值为1的时候，判断下一个结点的值是否为val，2 $\neq =$ 3，所以返回head.next为2所在的结点，所以返回head.next为2，构造子链表1–>2–>4–>5–>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 removeElements(ListNode head, int val) {
        //向下递归，如果为空则返回
        if (head==null) return null;
        //下面是单层的递归操作，将原始链表逐渐拆分成小的子链表,注意这里的返回值
        //返回值为head.next,所以head.next连接的是下一个子链表的头结点或者下一个子链表的头结点的下一个结点
        head.next = removeElements(head.next,val);
        //如果当前子链表的头结点的值为val,则返回头结点的下一个结点
        if (head.val==val){
            return head.next;
        }else{
        //如果当前子链表的头结点的值不为val,则返回当前头结点
            return head;
        }
    }
}

复杂度分析：
时间复杂度： $O (n)$
空间复杂度： $O (1)$

Leetcode 707 设计链表

题目链接: 设计链表
自己的思路：题目不难，理清加入，删除，查找的逻辑即可

正确思路:

代码:

//构造属于自己的链表(熟记)
class myListNode{
    int val;
    myListNode next;
    myListNode(){};
    myListNode(int val){
        this.val = val;
    };
}

class MyLinkedList {
    //存放链表的结点个数
    int size;
    //虚拟头结点
    myListNode dummyhead;

    //构造函数
    public MyLinkedList() {
        //初始化链表结点个数为0
        size = 0;
        //设置虚拟头结点，可以初始化为任何值
        dummyhead = new myListNode(0);
    }
    
    public int get(int index) {
        //如果索引不在链表中，直接返回-1
        if (index < 0||index >= size) return -1;

        myListNode cur = dummyhead;
        //因为是虚拟头结点，所以要走index+1步
        for (int i =0;i<=index;i++){
            cur = cur.next;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0,val);

    }
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    
    public void addAtIndex(int index, int val) {
        //索引不合法
        if (index > size) return;
        if (index<0){
            index=0;
        }
        //链表总长度加1
        size++;
        myListNode cur = dummyhead;
        //遍历到索引为index的结点的前一个结点
        //因为是虚拟头结点，所以要走index步
        for (int i =0;i<index;i++){
            cur = cur.next;
        }
        //新建一个需要加入的结点
        myListNode newindex = new myListNode(val);
        //加入结点
        newindex.next = cur.next;
        cur.next = newindex;
    }
    
    public void deleteAtIndex(int index) {
        //索引不合法
        if (index < 0||index >= size) return;
        //链表总长度减1
        size--;
        //如果删除头结点,则把虚拟头结点前进就可以了
        if (index==0) {
            dummyhead = dummyhead.next;
            return;
        }
        myListNode cur = dummyhead;
        //遍历到索引为index的结点的前一个结点
        for (int i =0;i<index;i++){
            cur = cur.next;
        }
        cur.next = cur.next.next;
    }
}

/**
 * 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);
 */