你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

力扣刷题——单链表系列——第一题:移除链表元素,从此链表初窥门径,神挡杀神~

2021-11-18 3:18:08

题目链接:力扣

力扣刷题——————>单链表系列

第一种解法:在原链表上进行操作,小红日烧脑版


/**



* 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 head;

        ListNode cur=head;

         ListNode ahead=null;

         while(cur != null)

        {

            if(cur.next != null)//首先当前的下一个不为空

            {

            ahead = cur.next;//调用先驱节点往前走,此句话保证了ahead一直在cur后面一位,紧跟着新cur

                if(ahead.val == val)//如果先驱节点的值正好等于目标值

                {

                    cur.next=ahead.next;//跨过ahead节点连接

                    ahead = cur;//先驱节点退回,等待下一次使用。

                }

            }

            if(cur.next != null && cur.next.val != val)

            {

                cur = cur.next;//cur能向前移动

                ahead = ahead.next;

            }

            if(cur.next == null)

            {

                if(head.val == val) return head.next;

                else break;

            }

        }

        return head;

}

}

关于本题解,补充说明如下,

//首先其实本题我的解法循环不变量设置的有问题很多情况下不论是数组还是链表
//快慢指针也好,滑动窗口也罢,其实极大多数都是将走的快的指针 一探到底设置为终止条件的

//循环不变量设置为cur,我的上述都是在while循环内针对cur.next不为空进行的操作,也就是最后cur.next==null的时候循环出不去了,所以需要进行处理!

//只有cur的下一个节点的值不为目标值,才能移动cur,所以到了此步(cur.next==null),不用再检查cur的val了

//拐回去判断一下头节点即可!~~因为一开始就是从cur和cur.next起始的,正好错过第一个头结点记得要在内部返回,不然报错死循环!也就是说你循环不变量找错了,需要手动退出~太菜了
//所以推荐大家用移动的快的指针做循环不变量终止循环!

根据本题,总结经验:

1:从一开始如果第一个头结点后是一连串符合要求需要删去的,那么要求你要么不断将指针回退,避免连续符合要求的情况,但是指针不断前进漏过去了:

要么跳过第一个头结点,扫描一遍再回头看第二个

2:while循环还是要找对循环不变量条件,出去的条件要考虑到

很多情况下不论是数组还是链表
//快慢指针也好,滑动窗口也罢,其实极大多数都是将走的快的指针 一探到底设置为终止条件的

找对条件事半功倍

3: 其次,如果起手一连串相同的,不如先考虑从第二个开始,然后再回头检查第一个,这种思想真的不错。


力扣刷题——————>单链表系列

第一题:移除链表元素


第二种解法:在原链表上进行操作,博哥版

此题某种意义上可以写成 单链表内的增删查改中的删除方法,remove属实高效。

更改了循环不变量!

/**
 * Definition for singly-linked list.
 * <p>
 * public class ListNode {
 * <p>
 * int val;
 * <p>
 * ListNode next;
 * <p>
 * ListNode() {}
 * <p>
 * ListNode(int val) { this.val = val; }
 * <p>
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * <p>
 * }
 */

class Solution {

//博哥解法

    public ListNode removeElements(ListNode head, int val) {

        if (head == null) return head;//只有在此判断是不是链表上来就为空,反手一个空,下面的引用变量就爆炸了,无法声明

        ListNode cur = head;//起手把用来穿的固定节点定在第一个

        ListNode ahead = head.next;//把先驱节点定在第二个

//到时候回头来检查第一个节点

//如果是 66666 val==6这种极端特判,从第一个开始检查太费劲,先驱结点需要不断退回~

        while (ahead != null)

//此处用ahead先驱节点做循环不变量,好处有三

//1:下面循环内的两种情况,不管何种,ahead的位置都在不断变更向前,当ahead为空,链表扫描一遍,复杂度为n

//2:如果是只有一个节点的情况,ahead就是空,进不去循环。

        {

            if (ahead.val == val)//如果先驱节点的值就是目标值,先跳过这个结点,然后再跟固定的穿起来

            {

                ahead = ahead.next;

                cur.next = ahead;

            } else//先驱节点安全,先往前再说,新ahead的值下次循环再判

            {

                cur = cur.next;

                ahead = ahead.next;

            }

        }//出了循环,然后再判断头结点

        if (head.val == val) {

            return head.next;

        }

        return head;

    }

}

第三种解法:论 链表的暴力解法!及其容易出现和发生的bug

  • 🔲不要忘了暴力解法声明新数组是一个一个结点申请copy往后加上的

力扣大佬,宫水三叶姐姐说过:链表 的 暴力解法 可以解决百分之九十的问题,

模板就是,申请一个新的头结点!ListNode newHead = new ListNode (-10),最后返回这个新头结点的 next,然后不断的copy不和条件的新节点添加到新链表中,最后再返回即可!~~

本题:力扣刷题——————>单链表系列

第一题:移除链表元素

第三种解法:申请链表,不断在后面动态更新加上原链表中符合要求的新的节点,三叶姐版

我的理解不深时候手敲的第一遍错误代码!

注意是错误的,大家看一看找出错误即可,浅尝辄止哦,不要上头!~

/**
 * Definition for singly-linked list.
 * <p>
 * public class ListNode {
 * <p>
 * int val;
 * <p>
 * ListNode next;
 * <p>
 * ListNode() {}
 * <p>
 * ListNode(int val) { this.val = val; }
 * <p>
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * <p>
 * }
 */

class Solution {

    public ListNode removeElements(ListNode head, int val) {

        if (head == null)

            return head;

        ListNode cur = head;

        ListNode newHead = new ListNode(-10);

        ListNode temp = newHead;

        while (cur != null) {

            if (cur.val != val) {

                temp.next = cur;

                temp = temp.next;


            }

            cur = cur.next;

        }

        return newHead.next;

    }

}

所以我是真的菜!然后第三种解法~

/**
 * Definition for singly-linked list.
 * <p>
 * public class ListNode {
 * <p>
 * int val;
 * <p>
 * ListNode next;
 * <p>
 * ListNode() {}
 * <p>
 * ListNode(int val) { this.val = val; }
 * <p>
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * <p>
 * }
 */

class Solution {

    public ListNode removeElements(ListNode head, int val) {

        if (head == null) {

            return head;

        }

        ListNode newHead = new ListNode(-10);

        ListNode temp = newHead;

        ListNode cur = head;

        while (cur != null) {

            if (cur.val != val) {

                ListNode node = new ListNode(cur.val);

                temp.next = node;

                temp = temp.next;

            }

            cur = cur.next;

        }

        return newHead.next;

    }

}