[LC]203题 Remove Linked List Elements （移除链表元素）（链表）

①英文题目

Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6

Output: 1->2->3->4->5

②中文题目

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6

输出: 1->2->3->4->5

③思路

1、加入链表为空，那么直接返回head。

2、考虑6,5,4,3,2,1，val=6.

所以，一开始就要判断头结点的值是否等于val。所以考虑用while或者if来写此处逻辑。

3、考虑，6,6,6,5,4,3,2,1，val=6

当我删除第一个6之后，后面又来一个6，所以，这个需要不停循环，直到首个元素不再是6.

所以大致是

 while(head!=null&&head.val==val){

         head=head.next;

 }

4、考虑 1->2->6->3->4->5->6, val = 6。

国际惯例，先让head赋给别的结点名，比如

 ListNode pre=head;//以后有什么事情，就在pre上做操作。而要return全部时，就return head

判断，如果pre.next的val和pre.next.next的val相等，那就把原本的pre.next删掉，代码写起来就是让pre的next不再指向pre.next，而是指向pre.next.next，

这个逻辑需要用一个while循环来写，while里保证pre.next存在，即不等于null。代码写起来就是

 while(pre.next!=null){

        if(pre.next.val==pre.next.next.val)

             pre.next==pre.next.next;   //看见一次next，就读作往后走了一个单位。

        else

             pre=pre.next;   //否则，让pre往后顺延一个单位

 }

④总的代码如下：

 class Solution {

     public ListNode removeElements(ListNode head, int val) {

         while(head!=null&&head.val==val)

             head=head.next;     //只有当头结点的val不再等于val时，才走出循环

         if(head==null)

             return head;

         ListNode pre=head;

         while(pre.next!=null){

             if(pre.next.val==val)

                 pre.next=pre.next.next;

             else

                 pre=pre.next;   //否则，让pre往后顺延1个单位

         }

         return head;

     }

 }

⑤

1、第一次见到连续两个.next；

2、几乎看见每一个链表题里，都会写一句把原本的头结点给赋给一个新声明的结点，比如ListNode pre=head;

当然，在这个赋值语句之前，先要保证head已经稳定了（比如本题总程序的3-4行就是在寻求一个稳定的head，不然，谁敢把不确定的head赋值给pre）。

⑥别人的“递归”代码：

  public ListNode removeElements(ListNode head, int val) {

         if (head == null)

             return null;

         head.next = removeElements(head.next, val);//先不管head.val是否等于val，而是先保证从第二个元素开始，去掉每个等于val的元素。

         if (head.val == val) {

             return head.next;

         } else {

             return head;

         }

     }

巴特西

[LC]203题 Remove Linked List Elements （移除链表元素）（链表）

最新文章

热门文章