移除链表中的元素

移除链表中的元素
移除元素的主要操作是将

  1. 找到待移除节点的前一个节点node
  2. 将 node 的指针域指向其下下个节点，即 待移除节点的下一个节点

注意事项：

  • 有头节点，移除头节点时，需单独分析
  • 删除重复的值时 使用while循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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) {
        // 删除头节点
         while(head!=null && head.val==val){
            head = head.next;
        }

        ListNode root = head;

        
        while(root != null)
        {   
            //使用while删除重复的值
            while(root.next!=null && root.next.val == val){
                ListNode temp = root.next;
                root.next = temp.next;
            }
            
            root = root.next;
            
        }

        return head;
    }
}

2.1 添加虚拟头节点

在删除链表元素时，由于头节点是没有前驱的，所以我们在删除时需要加入许多临界的判断。

使用虚拟头节点，相当于给头节点加入一个前驱，此时便可直接遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public ListNode removeElements(ListNode head, int val) {
       // 创建虚拟头节点
       ListNode pre = new ListNode(0);
       pre.next = head ;

       ListNode cur = pre;
       while(cur.next != null){
         //控制删除重复元素
           if(cur.next.val == val)
                cur.next = cur.next.next;

            else
                cur = cur.next;        
       }
       ListNode res = pre.next;

       return res;
    }
}