例二：鏈表中delete_ if

要求：

把所有數值為2的結點洗掉掉
在這里插入圖片描述
回圈從什么角度入手？
定義【回圈不變式】

假設第一個2已經被刪掉了
在這里插入圖片描述
怎么處理第2個2

思路：
Java：把3的next指向5，垃圾回收把結點2回收掉
C++：還需要delete結點2

具體怎么做？

有一個變數指向結點3
在這里插入圖片描述
把3指向5

不用管2

刪完2，下一個要考慮結點5，
此時previous指向3
在這里插入圖片描述
完成【回圈不變式】向前推進的程序

【回圈不變式】：

從鏈表開頭到previous結點為止，保證所有值為2的結點都已經被正確洗掉，

從previous結點的next進行考慮：

如果previous結點的next結點是2，把它洗掉；
如果previous結點的next結點不是2，把previous向后移一個，

如果第一個節點就是2，沒有previous，有2種處理方法：

在這里插入圖片描述

【一般情況】
Loop invariant: list nodes from head up to prev has been processed.
回圈不變式：從head開始一直到prev已經被完全處理掉
Processed——>(Nodes with values equal to value deleted)

While回圈體怎么寫

在這里插入圖片描述

封神操作！

在這里插入圖片描述

public static void main(String[] args)
	{
		LinkedListCreator creator = new LinkedListCreator();
		LinkedListDeletor deletor = new LinkedListDeletor();

		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(Arrays.asList(1, 2, 3, 2, 5)), 2));

		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(Arrays.asList(1, 2, 3, 2, 2)), 2));

		// 洗掉頭結點
		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(Arrays.asList(1, 2, 3, 2, 2)), 1));

		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(Arrays.asList(2, 2, 3, 2, 2)), 2));

		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(Arrays.asList(2, 2, 2, 2, 2)), 2));

		// 單點
		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(Arrays.asList(2)), 2));
		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(Arrays.asList(2)), 1));

		// 空集
		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(new ArrayList<Integer>()), 1));

		// 列印linked list，見Node.java
	}