leetcode 203号问题
1 2 3 4 5 6
|
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
|
给定的节点
1 2 3 4 5 6 7 8 9
|
public class {
public int val; public ListNode next;
public (int x) { val = x; } }
|
不使用虚拟头结点
如果链表头部是需要删除的元素, 直接进行删除, 直到整个链表删除完或者链表头不是需要删除的元素为止; 然后开始删除头结点后面需要删除的元素
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
|
class Solution { public ListNode removeElements(ListNode head, int val) {
while(head != null && head.val == val){ ListNode delNode = head; head = head.next; delNode.next = null; }
if(head == null) return head;
ListNode prev = head; while(prev.next != null){ if(prev.next.val == val) { ListNode delNode = prev.next; prev.next = delNode.next; delNode.next = null; } else prev = prev.next; }
return head; } }
|
另一种方法是既然头部是需要删除的节点, 就直接跳过去, 不去管它, 那么整个链表剩下的就是头结点不需要删除的了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
|
public ListNode removeElements(ListNode head, int val) {
while(head != null && head.val == val) head = head.next;
if(head == null) return head;
ListNode prev = head; while(prev.next != null){ if(prev.next.val == val) prev.next = prev.next.next; else prev = prev.next; }
return head; }
|
使用虚拟头结点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
|
public ListNode removeElements(ListNode head, int val) {
ListNode dummyHead = new ListNode(-1); dummyHead.next = head;
ListNode prev = dummyHead; while(prev.next != null){ if(prev.next.val == val) prev.next = prev.next.next; else prev = prev.next; }
return dummyHead.next; }
|
递归
本质上是将原来的问题转化为更小的同一问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|
public ListNode removeElements(ListNode head, int val) { if(head == null) return head;
ListNode res = removeElements(head.next, val);
if(head.val == val) return res; else{ head.next = res; return head; } }
|
化简
1 2 3 4 5 6 7 8
|
public ListNode removeElements(ListNode head, int val) {
if(head == null) return head;
head.next = removeElements(head.next, val); return head.val == val ? head.next : head; }
|
其他结构的链表
双向链表
在双向链表中, 每个节点都有两个指针, 一个指向下一个节点, 一个指向前一个节点
1 2 3 4 5 6 7 8 9
|
class Node{ E e; Node next, prev; }
|
循环链表
循环链表的尾结点指向的是头结点
1 2 3 4
|
class Node{ E e; Node next, prev; }
|
数组链表
使用数组来实现链表, 存储的是元素和下一个节点的下标
1 2 3 4
|
class Node{ E e; int index; }
|
完整代码
近期评论