习惯github pages风格的请看我的另一篇博客
题目18：
- 在O(1)的时间内删除链表节点
- 删除链表中重复的节点
题目1：在O(1)的时间内删除链表节点
给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。
举例说明
链表1->2->3，输入头结点head和待删除结点n2，输出删除之后的头结点，此时链表1->2。
思路
1. 从头遍历（暴力）
- 一般单向列表删除结点，就是从头遍历，
找到这个结点之前的结点，指向这个结点之后的结点，就算是删除了这个结点。 - 这种方法的
时间复杂度O(n)
2. 复制结点法
- 题目要求在O(1)时间内完成，所以应该避免遍历。
- 我们
遍历的目的是为了找到这个结点前面的那个结点，所以我们可以 将待删除结点的下一个结点的值赋给待删除的结点，然后删除一个结点，就达到了删除结点的目的。（实际被删除的是待删除节点的下一个节点nodeToBeDeleted.next） - 对于n-1个非尾节点，O(1)时间内可以删除，如果是尾节点则O(n)，平均时间复杂度为[O(1)∗(n−1)+O(n)∗1]/n，时间复杂度还是O(1)。符合要求。不过该方法并没有判断需要删除的节点是否在链表中，为达到时间复杂度为O(1)的要求，将判断节点是否存在的责任推给了该方法的调用者。
注意边界条件的特殊处理
1)正常, 多个结点，删除的不是尾结点。
2)只有一个结点，删除尾结点（也是头结点）
3)有多个结点，删除尾结点
具体逻辑
- 要删除的节点不是尾节点
时间复杂度O(1) - 要删除头节点，而且链表只有一个节点
时间复杂度 O(1) - 要删除尾节点，而且链表有多个节点
时间复杂度 O(n)
代码实现
public class _18_1 {
private static class ListNode {
int val;
ListNode next;
ListNode() {
};
ListNode(int value) {
this.val = value;
}
}
// 这个方法和文本上的返回值不一样，书上的没有返回值
//因为JAVA值传递的原因， 如果删除的结点是头结点，如果不采用返回值的方式，那么头结点永远删除不了
private static ListNode deleteNode(ListNode head, ListNode nodeToBeDeleted) {
if (head == null || nodeToBeDeleted == null)
return head;
//1. ------------------------------------------------------------
if (nodeToBeDeleted.next != null) {
nodeToBeDeleted.val = nodeToBeDeleted.next.val;
// 待删除的结点的下一个指向原先待删除引号的下下个结点，即将待删除的下一个结点删除
nodeToBeDeleted.next = nodeToBeDeleted.next.next;
} //2. ------------------------------------------------------------
else if (head == nodeToBeDeleted) {
return head.next;
}
else {//3. ------------------------------------------------------------
ListNode tmp = head;
while (tmp.next != nodeToBeDeleted) {
tmp = tmp.next;
}
tmp.next = null;//尾结点前一个指针指向空
nodeToBeDeleted = null;//尾结点空
}
return head;
}
private static void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + "-> ");
head = head.next;
}
System.out.println("null");
}
public static void main(String[] args) {
// 多个节点，并且删除的不是尾结点
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
n1.next = n2;
n2.next = n3;
System.out.println("多个节点，并且删除的不是尾结点--------");
System.out.println("调用前");
printList(n1);
System.out.println("调用后");
printList(deleteNode(n1, n2));
// 只有一个节点
System.out.println("只有一个节点----------");
ListNode n4 = new ListNode(4);
System.out.println("调用前");
printList(n4);
System.out.println("调用后");
printList(deleteNode(n4, n4));
// 多个节点，删除尾结点
ListNode n5 = new ListNode(5);
ListNode n6 = new ListNode(6);
ListNode n7 = new ListNode(7);
n5.next = n6;
n6.next = n7;
System.out.println("多个节点，删除尾结点------------");
System.out.println("调用前");
printList(n5);
System.out.println("调用后");
printList(deleteNode(n5, n7));
}
}
输出
在O(1)的时间内删除链表节点
题目2：删除链表中重复的节点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
举例说明
链表1->2->3->3->3->4->4>5，输入头结点head，输出删除之后的头结点，此时链表1->2>5。
思路
哪些可以被删除
我们从头遍历整个链表。如果当前结点的值与下一个结点的值相同，那么它们就是重复的结点，都可以被删除
怎么删除
为了保证删除之后的链表仍然是相连的而没有中间断开，我们要把当前的前一个结点和后面值比当前结点的值要大的结点相连。
我们要确保prev要始终与下一个没有重复的结点连接在一起
考虑边界
-
头结点可能与后面的结点重复，也就是说头结点也可能被删除，所以在链表头添加一个结点
具体
- 两链表相连且val一样，我们可看做重复结点，那么我们将两者同时删除
- 每次while之后，
node先永远指在值分界点的右边
- 如果当前结点的值与下一个结点的值相同，那么它们就是重复的结点，都可以被删除
1.1 找到下一个不同值的节点：直到node.next.val != node.val，注意其有可能也是重复节点
1.2 指向下一个节点，prev.next也可能是重复结点，所以prev不要移动到下一个结点 - 相邻两个值不同，说明node不可删除，要保留
代码
public class _18_2 {
private static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int value) {
this.val = value;
}
}
private static ListNode deleteDuplication(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
ListNode root = new ListNode();
root.next = head;// 临时的头结点
ListNode prev = root;// 记录前驱结点
ListNode node = head;// 记录当前处理的结点
while (node != null && node.next != null) {//while.if.while
//1-------------------------------------------
if (node.val == node.next.val) {
while (node.next != null && node.next.val == node.val) {
node = node.next;
}
//1.2----------------------------------------
prev.next = node.next;//这里完成删除，指针跳跃
}else {//2-------------------------------------------
prev.next = node;
prev = prev.next;
}
node = node.next;
}
return root.next;
}
private static void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + "->");
head = head.next;
}
System.out.println("null");
}
public static void main(String[] args) {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(3);
ListNode n5 = new ListNode(3);
ListNode n6 = new ListNode(4);
ListNode n7 = new ListNode(4);
ListNode n8 = new ListNode(5);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n7;
n7.next = n8;
System.out.println("调用前");
printList(n1);
System.out.println("调用后");
printList(deleteDuplication(n1));
}
}
输出
删除链表中重复的节点
