Leetcode 203 移除链表元素
准备工作
1）ListNode基本结构
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
@Override
public String toString() {
ListNode node = this;
StringBuilder sb = new StringBuilder();
while (node != null) {
sb.append(node.val).append("->");
node = node.next;
}
sb.append("NULL");
return sb.toString();
}
}
2）初始化ListNode集合
public class ListNodeInit {
public static ListNode getInitList() {
ListNode tailf = new ListNode(5, null);
ListNode node4 = new ListNode(4, tailf);
ListNode node3 = new ListNode(3, node4);
ListNode node2 = new ListNode(2, node3);
return new ListNode(1, node2);
}
}
解法一：遍历判定
使用两个指针s1、s2来定位链表中的数据，遇到val相等时，就移除对应的节点，否则就依次向后移动节点
class Solution {
public static void main(String[] args) {
ListNode initList = ListNodeInit.getInitList();
System.out.println(initList);
System.out.println("-----删除后-----");
System.out.println(removeElements(initList, 2));
}
public static ListNode removeElements(ListNode head, int val) {
// 构建一个哨兵节点，可以避免后续的空节点、只有一个节点等特殊case
ListNode node = new ListNode(-1, head);
ListNode s1 = node;
ListNode s2 = node.next;
while (s2 != null) {
if (s2.val == val) {
s1.next = s2.next;
} else {
s1 = s1.next;
}
s2 = s2.next;
}
return node.next;
}
}
解法二：递归判定
递归链表为基础，分别处理val值相等和不相等的情况。
- 相等时：即代表我们返回的head数据不包含当前节点，即直接进入next节点的判定
- 不相等时：当前节点保留，即head.next的关联关系依然存在，即进行head.next节点的判定，head.next=表示不丢弃当前节点
class Solution {
public static void main(String[] args) {
ListNode initList = ListNodeInit.getInitList();
System.out.println(initList);
System.out.println("-----删除后-----");
System.out.println(removeElements(initList, 2));
}
public static ListNode removeElements(ListNode head, int val) {
if (head == null) {
return null;
}
if (head.val == val) {
// 赋值next则代表移除一个node节点
return removeElements(head.next, val);
} else {
// head.next可以将返回的节点进行关联
head.next = removeElements(head.next, val);
return head;
}
}
}
