链表经典面试题_链表面试题

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

OJ链接

删除节点的核心是：需要找到这个节点的前一个节点是谁

思路：

定义两个变量prev，cur，prev从head开始，cur从head.next开始prev代表cur的前驱，头节点留在最后处理 ,cur遍历整个链表如果cur.value==key,就让pre.next=cur.next,之后cur=cur.next,否则pre=cur，cur=cur.next

时间复杂度O(N)

经过上面的删除后，因为cur是从head.next开始遍历的，所以最后需要检查头节点是否是要删除的节点，如果是head=head.next即可
⭐️

  public ListNode removeElements(ListNode head, int val) {
           
       if(head==null){
            return null;
        }
      ListNode pre=head;
       ListNode  cur=head.next;
        while (cur!=null){
            if(cur.val==val){
                pre.next=cur.next;
                cur=cur.next;
            }else {
                pre=cur;
                cur=cur.next;
            }
        }
        if(head.val==val){
            head=head.next;
        }

        return head;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.反转单链表

OJ链接
思路：