LeetCode 203 Remove Linked List Elements 题解

发表于 | 阅读次数:

题目

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

　　Example

　　Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6

　　Return: 1 –> 2 –> 3 –> 4 –> 5

思路

　　这道题非常简单，但很好地体现了单链表的特点。单链表每个结点只能引用下一个结点，因此删除结点时，也只能立足于一个不需要被删除的结点，去判断是否需要删除下一个结点。

　　由于删除时候需要遍历链表，但遍历的开始必须是头结点，而头结点如果要删除就要额外处理了。这里我们在头结点之前再插入一个临时结点，以统一处理整个链表。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        while(head.next != null){
            if(head.next.val == val){
                head.next = head.next.next;
            }else{
                head = head.next;
            }
        }
        return dummy.next;
    }
}

　　代码里删除只针对紧邻的下一个结点。当下一个结点的值是需要删除的值时，则删除下一个结点，再判断新的下一个结点是否需要删除；如果下一个结点不需要删除，则移动到下一个结点，再观察后面的结点是否需要删除。